LeetCode problem #454 — 4Sum II (JavaScript)

In this LeetCode problem, we’re given an array of numbers and asked to find the number of combinations — made by taking 1 number from each array — that when added together total 0.

In other words, when given the following arrays:
A: [2, 6]
B: [1, 2]
C: [-1, 9]
D: [-2, 7]
The answer would be 1, as the only combination would be 2 from A, 1 from B, -1 from C and -2 from D, all of which add together to make 0.

Solution #1: Brute force

Predictable however, this approach is very slow. In fact because it has 4 recursive 4 loops, the runtime complexity is an eye-watering O(N⁴).

Solution #2: Map

First, we loop through the A and B loops with a nested for loop, and calculate all potential values for these 2 arrays. We then store these values in a Map, ready to be called upon later. In addition, we also record the number of times these solutions are each found, which we will again use later.

Next we loop through arrays C and D, this time calculating the target value, or complement (which is the opposite of the sum of values for each combination). In other words, if we’re adding 2 + 3, and need to get back to 0, our sum will be 5, and thus our target or complement will be -5.

Finally we look in our Map to see if said complement has already been recorded. If it has, we add the number of times that combination was found in the first dual-loop to a running total of combinations, which we then return at the end of the function.

This solution isn’t especially elegant, but it is efficient. Due to the use of dual nested loop, it has a runtime complexity of just O(N²), rather than O(N⁴) seen from the first approach.

Full-stack software developer from the UK, author of the Aftermath book series, full time tech-nerd.