Using JavaScript and the Two‑Pointer Technique to Solve 4Sum

Following on from my recent articles solving the 2sum and 3sum problems with JavaScript, it makes perfect sense that we now delve into the next problem in the sequence: the 4Sum problem.

As with other LeetCode‑type problems, these are classic interview questions: challenges that require some creative thinking alongside a solid understanding of array manipulation and classic algorithmic strategy.

As with the sibling 2/3Sum problems, the solution lies in implementing the two‑pointer technique, a strategy which can efficiently tackle various array‑related problems.

Understanding the 4Sum Problem

The 4Sum problem is a variation on the well‑known 2Sum and 3Sum (or Two Sum and Three Sum) problems.

In this instance, we're given an array of integers and a target value and then asked to find all unique quadruplets in the array that sum up to the given target. It's important to note here that I've often seen two variations of this (and the 2/3Sum counterparts) where the expectation is that the returns sum up to zero, rather than requiring an additional target input. For 4Sum though, let's accept a target too.

An Example

For a more clear example, let's say that we have the array: [1, 0, ‑1, 0, ‑2, 2] and the target sum 0.

We would expect our function to produce the quadruplets [‑2, ‑1, 1, 2] and [‑2, 0, 0, 2] ‑ in both quadruplets, the total sum is the target: zero.

The Two‑Pointer Technique

Our weapon of choice to solve the 4Sum problem ‑ much like before ‑ is the two‑pointer technique. This technique involves sorting the array and then using two pointers to navigate through the array from one end to the other in a way that reduces the search space whilst trying to find the desired sum.

How the Two‑Pointer Technique Works in Practice

1. Sort the array in ascending order.
2. Iterate through the array with two pointers: one starting from the left (low), and the other starting from the right (high).
3. Calculate the sum of the elements at the current low and high positions, as well as the other two pointers in between.
4. If the sum is equal to the target, we've found a valid quadruplet.
5. If it's less than the target, we move the low pointer to the right.
6. If it's greater, we move the high pointer to the left.
7. Continue iterating and adjusting the pointers until the low pointer is less than the high pointer.

Implementing a Solution Using JavaScript (and TypeScript)

Given my field, it will come as no surprise that I'm going to offer a solution using front‑end technologies. Here's a rough solution:

const fourSum = (nums: number[], target: number): number[][] => {  const result: number[][] = [];  const n: number = nums.length;  nums.sort((a, b) => a - b);  for (let i = 0; i < n - 3; i++) {    if (i > 0 && nums[i] === nums[i - 1]) continue;    for (let j = i + 1; j < n - 2; j++) {      if (j > i + 1 && nums[j] === nums[j - 1]) continue;      let low = j + 1;      let high = n - 1;      while (low < high) {        const sum = nums[i] + nums[j] + nums[low] + nums[high];        if (sum === target) {          result.push([nums[i], nums[j], nums[low], nums[high]]);          while (low < high && nums[low] === nums[low + 1]) low++;          while (low < high && nums[high] === nums[high - 1]) high--;          low++;          high--;        } else if (sum < target) {          low++;        } else {          high--;        }      }    }  }  return result;};

By sorting the array and using the two‑pointer technique, this efficiently explores all possible combinations whilst attempting to avoid duplicates. The algorithm's time complexity is O(n^3) due to the nested loops, and the space complexity is O(1) since we're using a constant amount of extra space.

Adding Some Tests

As I've covered previously, it is always worth offering some test coverage when writing functionality like this, not least because it might make your application stand out against the others!

In the same vein as I wrote for the 3Sum problem, here are some quick Cypress tests:

describe('4Sum', () => {  it('should find all unique quadruplets that sum up to zero', () => {    expect(fourSum([-1, 0, 1, 2, -1, -4], 0)).toEqual([      [-4, -1, 1, 4],      [-4, 0, 0, 4],      [-4, 0, 1, 3],      [-4, -1, 0, 5],      [-1, -1, 0, 2],      [-1, -1, 1, 1],    ]);    expect(fourSum([0, 0, 0, 0], 0)).toEqual([[0, 0, 0, 0]]);    expect(fourSum([-2, 0, 0, 2, 2], 0)).toEqual([      [-2, 0, 2, 0],      [-2, 0, 0, 2],    ]);  });  it('should find all unique quadruplets that sum up to the target', () => {    expect(fourSum([-1, 0, 1, 2, -1, -4], 1)).toEqual([      [-4, 0, 1, 4],      [-1, -1, 1, 2],    ]);    expect(fourSum([0, 0, 0, 0], 0)).toEqual([[0, 0, 0, 0]]);    expect(fourSum([-2, 0, 0, 2, 2], 0)).toEqual([      [-2, 0, 2, 0],      [-2, 0, 0, 2],    ]);  });  it('should handle empty and small arrays', () => {    expect(fourSum([], 10)).toEqual([]);    expect(fourSum([1], 10)).toEqual([]);    expect(fourSum([1, 2], 10)).toEqual([]);  });});

Wrapping‑Up

So there you have it! We've explored the 4Sum problem, dived into the two‑pointer technique, and implemented a solution in JavaScript using ES6 and TypeScript. Remember, understanding classic algorithmic problems and efficient solutions can greatly enhance your problem‑solving skills. Plus, testing your code using tools like Cypress ensures its reliability.