Meet in the middle

Meet in the middle (sometimes called split and merge) is a clever approach which tries to trade off space for time. Much like divide et impera it divides the problem in two and then tries to merge the results. The result usually is that by using quite a bit of memory you can tackle problems of twice size you could before.

Let’s discuss a few applications.

4sum

Given an array of integers, find out if there are any four numbers such that the sum of the first three equal to the fourth (you can use the same number more than once).

The naive algorithm is O(N⁴) try all the possible combinations of four numbers. A less naive algorithm brute forces through all n³ combinations of three numbers and then efficiently checks if their sum is in the original array by using a hash table.
But by now you’ve probably started thinking how meet in the middle can be applied for this problem. The trick is to rewrite the equation as a + b = d - c. Store all the n² sums a + b in a hash set S. Then iterate through all n² combinations for c and d and check if S contains d - c. This algorithm has O(n²) time and space complexity.

Breaking 2DES

DES is a encryption standard which uses 56 bit keys. This was enough when the algorithm got invented but currently computers can use a brute force approach to break the encryption. One simple idea to make the encryption more secure is to apply the encryption twice using two different keys. This approach is susceptible to the meet in the middle attack developed by Diffie Hellman. So currently 3DES is used which uses three keys and encrypts the message three times.

Let’s see why 2DES is bad. We call Ek the encryption function using the secret key k and Dk the decryption function using the secret key k. 2DES uses Ek1) = s to encrypt and Dk2) = p to decrypt.

Diffie Hellman’s meet in the middle attack trades of space for time to find out the two secret keys.
For the pattern p it tries all the possible keys to obtain a set of numbers corresponding Ek(p). Also for the pattern s it uses all the possible keys to decrypt s, Dk(s).
If we find any match in the two sets it means that Ek1 = Dk2 so the secret keys are k1 and k2.
The naive brute force algorithm would go through 2⁵⁶ * 2⁵⁶ iterations by brute forcing through all possible values of k1 and k2 while this algorithm uses 2⁵⁶ * 56 memory to store Ek(p) and does O(2⁵⁶) work to find a match.

Discrete logarithm

Given n a prime number and p, q two integer numbers between 0 and n-1 find k such that p^k = q modulo n.

This problem can be solved using the baby step, giant step algorithm which uses the meet in the middle trick.
We can write Notice that i <= sqrt(n) and j <= sqrt(n).
Now our equality looks like this p ^{(i ([sqrt(n)] + 1) + j) = q modulo n. We can divide by p}j and get p^{(i[sqrt(n)] + 1) = qp}-j modulo n.
Now the application of meet in the middle becomes obvious. We can brute force through the numbers on each side of the equality and find a match.
The algorithm takes O(sqrt(n)) space and O(sqrt(n)) time.

Bidirectional search(interview question)

Find the shortest path between two nodes nodes in a large graph which you can’t keep in memory, for example the Facebook friendship graph.

One neat idea is instead of starting the search from one node, start from both and see when the two search spaces meet. If the distance between two nodes is k and the average branching factor in the network is p then we explore O(p^k/2) nodes instead of O(p^k) nodes.

Caveats

Unlike divide and conquer the trick in meet in the middle can't be applied recursively because the sub problems don't have the same structure as the original problem.
Bidirectional search can be often replaced by some search algorithm that uses some heuristics like A*.

Additional problems

1. Friend of a friend(interview question): Given two user names in a social network find design an efficient way to test if one is a friend of a friend of the other.
2. Equal partition: Given a set A of 40 real numbers, find out if there is any way to split A in two sets such that the sums of their elements are equal. (Hint: complexity O(2^n/2))
3. Minimal vertex cover: Given a graph of n nodes (n <= 30), find out a set with the smallest number of vertices such that each edge in the graph has at least one node inside the set. (Hint: complexity O(3^n/2))
4. Square: You're given an array L which represents the sizes of n planks. You have to answer if there's any way to form a square using the planks without breaking them of overlapping them. (Hint: complexity O(4^n/2))
5. 8 puzzle: The 8 puzzle is a sliding tile puzzle of 3×3 slots with 8 tiles and one empty slot. At each step you can move one of the orthogonaly neighbouring tiles to the empty slot. The game starts from a random initial configuration and the purpose is to get to the * in the fewest number of moves. Figure out an efficient algorithm that solves the 8 puzzle. (Hint: Each position is solvable in at most 31 moves) In the picture we see a sequence of moves that solves the puzzle.
   

Try the to solve these problems in the comment section.