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
The obvious brute force solution to this problem is to run 4 for loops, one for each of the supplied arrays. By doing this, we can add together every potential combination of values from the 4 arrays to find out the total number of potential combinations.
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
Much like with previous x-sum solutions, we’ll employ the use of a Map in order to avoid looping through all of the data in an inner loop.
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.