Solving The Four Number Sum Problem in JavaScript

The Prompt

Create a function that takes a non-empty array of distinct integers and an integer representing a target sum.

The function should find all the quadruplets in the array, of which the sum is equal to the target sum.

Return a two-dimensional array of all these quadruplets in no particular order.

If there are no quadruplets that add up to the target sum, return an empty array.

The Approach

Starting off, we have to think about how to track the combinations of the elements in the input array. One way I always go to is to create an object that will store pairs of sums and an empty array where we can push the quadruplets into.

Then, using for loops, we can create variables for the current sum as well as a variable to keep track of the difference. If the difference happens to be in the object we previously created to keep track of all he pair sums, then we can push the values into the final array.

We can initiate another for loop to traverse the input array and create another current sum variable within the scope of this for loop. So at this point, there is a main for loop, with two nested for loops, and I’m talking about the second loop.

If the current sum isn’t in the object, then we can set the values to the index of the current sum. Otherwise, we can push the pair into the object at the index of the current sum.

Finally, outside of the for loops, we can return the quadruplets.

Let’s work on the actual code now.

The Code

Initiate the function with the correct parameters.

Then let’s create the containers so we can keep track of the sums.

Now lets’s create the initial for loop as well as the nested for loop, so we can have indices that act as “pointers” to point to a specific element.

Now, within the nested for loop, let’s create the variables for the current sum and the difference.

Now, we can start an if statement to check if the difference is in the allPairs object. If it is, we can push the values into the final quadruplets array. It’ll look like this.

Now, we can initiate the second for loop, as per the scope of the first for loop on line 4, to create another pointer which will be “k” for this problem. We’ll create another current sums variable for this for loop. K will be compared to the initial (i) index of the first for loop and will always be at a position before the (i).

Now we can use an if/else statement to check whether the current sum is in the allPairs object, if it’s not, set the values in the object, else push the pair into the allPairs object.

Finally, we can return the quadruplets array. The final solution will look like the following:

Complexity Analysis

In worst case scenario, the time complexity of this solution would be O(n³) time.

The space complexity would be O(n²) space.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store