h1. 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 benefit is that by using quite a bit of memory you can tackle problems of twice size you could before.

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 benefit is that by using quite a bit of memory you can tackle problems of twice the size you could before.

Let’s go through a few applications.

Here are a few applications.

h2. 4sum

bq. Given A, an array of integers, find out if there are any four numbers such that their sum equals zero (you can use the same number more than once). For example given A = [2, 3, 1, 0, -4, -1] a solution is 3 + 1 + 0 - 4 = 0 or 0 + 0 + 0 + 0 = 0.

bq. Given A, an array of integers, find out if there are any four numbers in the array that sum up to zero (the same element can be used multiple times). For example given A = [2, 3, 1, 0, -4, -1] a solution is 3 + 1 + 0 - 4 = 0 or 0 + 0 + 0 + 0 = 0.

The naive algorithm tries all the possible combinations of four numbers. This solution takes $O(N^4^)$ time.

The naive algorithm checks all four number combinations. This solution takes $O(N^4^)$ time.

A less naive algorithm brute forces through all $n^3^$ combinations of three numbers and then efficiently checks if -(a + b + c) is in the original array using a hash table. This algorithm has $O(n^3^)$ complexity.

A slightly improved algorithm brute forces through all $n^3^$ three number combinations and efficiently checks if -(a + b + c) is in the original array using a hash table. This algorithm has $O(n^3^)$ complexity.

By now, you’ve probably started thinking how meet in the middle can be applied to this problem. The trick is to rewrite the equation as $a + b = -(c + d)$. Store all the $n^2^$ sums $a + b$ in a hash set $S$. Then iterate through all $n^2^$ combinations for c and d and check if $S$ contains -(c + d).

By now, you’ve probably started thinking how the meet in the middle technique could be applied to this problem. The trick is to rewrite the equation as: $a + b = -(c + d)$. Store all the $n^2^$ sums $a + b$ in a hash set $S$. Then iterate through all $n^2^$ combinations for c and d and check if $S$ contains -(c + d).

Here's how the code looks