Meet in the middle: hacking exponential time complexity
The passages in this article can be found on page 57 of the “The Competitive Programmer’s Handbook”. Other excepts and material taken from Polylog’s youtube video on the subject.
Introduction
There’s something about exponential time complexity that really bothers me. If you frequent the training grounds of leetcode, you’ll know the feeling: often times they’re the result of some nasty brute-force approach (ugh), like checking every state of some combination for example.
This is not to be confused with polynomial time complexity, where the exponent is a constant value (and is thus, stomachable); with exponential time complexity the exponent term grows with the input size (ie. O(n²) vs O(2ⁿ)).
As such, there are times where I find myself staring at a leetcode question for over an hour, with hands on my head desperately trying to summon the “right” answer in my mind. Meanwhile, the code editor sits empty; staring back with its default code template left untouched beside a blinking cursor. Defeated, I’m always astonished when I end up clicking the ‘solution’ tab and the first thing I see is: Approach 1: Brute Force (Accepted).
As with many problems, sometimes a brute force approach is simply the only solution. And if that brute force approach requires exponential time complexity, so be it; there’s nothing to be done.
Or is there?
Breadth-First Search
Let's first step back and imagine we’re trying to devise an algorithm to solve a rubik’s cube. We can assume that each unique configuration of the cube represents a state; and that different states are connected by physically possible moves.
We can use a breadth-first search algorithm to search adjacently connected states. In this way, we explore all the states that we can reach from our original scrambled configuration with one move, then all the states we can reach with two moves, and so on. The amount of states we will have to explore with each move increases exponentially: if there are 18 possible moves for every state, then the amount of states will multiply by 18 for each move (slightly less in reality since certain moves can ‘undo’ previous moves).
We can keep exploring states from our scrambled configuration until we arrive at a solved configuration state. Thus, we have found some path, or some sequence of moves, that solves the cube. The problem with this approach is that it is painfully slow.
It should be noted that our approach also works in reverse. Searching from a solved state and trying to find our original scrambled configuration is an equivalent solution that also works; albeit just as slowly.
In order to explore all states we can reach with just 5 moves, we need to calculate approximately 2 million states; for 10 moves, that number jumps to 3 trillion states.
Sometimes, you’ll just have to accept this. In our search for speed; we may find ourselves solving nothing at all. Ultimately, certain problems have no better solution than a slow one. Luckily, this is not one of those problems.
Meet in the Middle
Instead of starting from our known scrambled configuration and performing BFS (breadth-first search) until we explore the solved configuration, we can try two separate instances of BFS; one starting from the scrambled configuration and the other starting from the solved configuration. We will then perform one iteration of BFS at a time for each instance until they, “meet in the middle”, so to speak. In essence, we will be performing the original algorithm twice, at half the moves.
The reason this is so powerful is because our search space grows exponentially. By cutting the amount of moves in half, our search space is decreased exponentially in the same way; even if we perform the entire operation twice. We can actually prove that the time complexity with this method is improved.
Calling ‘meet in the middle’ an algorithm would be too limiting. A more fitting label might be an approach. We might be tempted to reduce the scope of this approach; perhaps we may deduce that some starting and target state is required in order to perform “meet in the middle.” We’ll go over another very different example that will demonstrate the contrary.
Combination Sum
Our next example comes from “The Competitive Programmer’s Handbook”. We’re given a list of n numbers and some target number x, and we want to figure out if there is some combination of numbers in the list that add up to x, otherwise called a combination sum.
Given the list [2, 4, 5, 9] and a target 15, we can choose [2, 4, 9] from the list to get 15. If our target was 10, there would be no solution.
A brute-force solution to this problem involves generating each subset of numbers and checking if the sum of each subset equals the target x. We can generate all subsets of a list and perform the check in O(2ⁿ) time complexity. Once again, we’ve arrived at solution that we would like to optimize.
The Competitive Programmer’s Handbook describes it’s implementation of ‘meet in the middle’ as follows:
The idea is to divide the list into two lists A and B such that both lists contain about half of the numbers. The first search generates all subsets of A and stores their sums to a list Sa. Correspondingly, the second search creates a list Sb from B. After this, it suffices to check if it is possible to choose one element from Sa and another element from Sb such that their sum is x. This is possible exactly when there is a way to form the sum x using the numbers of the original list.
For example, suppose that the list is [2, 4, 5, 9] and x = 15. First, we divide the list into A = [2,4] and B = [5,9]. After this, we create lists SA = [0,2,4,6] and SB = [0,5,9,14]. In this case, the sum x = 15 is possible to form, because SA contains the sum 6, SB contains the sum 9, and 6 + 9 = 15. This corresponds to the solution [2,4,9].
Essentially, we’re suggested to split the input list in half; generating a list of all possible combination sums for each half of the list. With these two ‘sum-lists’ the problem can be thought of as a modified Two Sum problem. It is a very well known problem and can be solved in linear time complexity. Details about the Two Sum problem won’t be discussed in detail, but an implementation would likely store one of the ‘sum-lists’ in a dictionary and check for keys while iterating over the other ‘sum-list.’
As a result, our solution now much faster for reasons explained earlier. We perform our O(2ⁿ) combination sum algorithm on two lists that are half as long. The additional linear computation on top of our generated lists is inconsequential.
Hence, we are able to take an algorithm with exponential time complexity and improve it’s speed drastically by performing the same algorithm twice on two halves of the input. In this example, we’re not exactly trying to find a path between two selective states, so ‘meet in the middle’ doesn’t have it’s visual analogy here. Accordingly, we should generalize ‘meet in the middle’ as an approach where we divide the input space into two equal parts, combining the two solutions together by leveraging some mathematical or logical tactic.
I should mention that while I spent the majority of this article bashing exponential time complexity, you’ll find that ‘meet in the middle’ is also an effective approach for optimizing polynomial time complexity solutions as well. The proof for this, is of course, left as an exercise to the reader.
Closing and Acknowledgements
‘Meet in the middle’ is a powerful tool that you should add to your arsenal. Being able to recognize when this approach is a viable solution can make a huge difference between what software solutions may be feasible in the real-world; yes, even beyond solving leetcode problems (See: DES/3DES, and why 2DES isn’t a thing).
Naturally, these insights also translate to leetcode and any challenges you might face in technical interviews. Hopefully, this article played a key role in helping you with any of the above.
This article wouldn’t have been possible without Polylog’s youtube video on meet in the middle, and their video is part of what inspired me to write this piece. If you have the time, check out their channel for more interesting math/logic/programming related content.