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 expect [-2, -1, 1, 2], [-2, 0, 0, 2] and [-1, 0, 0, 1]. Each quadruplet adds up to the target, 0.

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. Use nested loops to fix the first two indices, i and j. Search the remaining suffix with low = j + 1 and high = nums.length - 1.
3. Add nums[i], nums[j], nums[low] and nums[high]. All four positions are distinct.
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 whilst low < high. Stop that search when the pointers meet or cross, and skip repeated values as shown in the implementation.

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;
};

The two fixed indices and the remaining pointer search give O(n³) worst‑case time. The pointers and counters use constant auxiliary space, but the returned quadruplets and the sorting implementation need additional storage. This version also sorts nums in place, so it changes the input array.

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!

Here are some Cypress tests using its Chai expect assertions. Import fourSum from the module containing the implementation before running them in your test suite:

describe('4Sum', () => {
  it('finds the unique ordered quadruplets for a zero target', () => {
    expect(fourSum([1, 0, -1, 0, -2, 2], 0)).to.deep.equal([
      [-2, -1, 1, 2],
      [-2, 0, 0, 2],
      [-1, 0, 0, 1],
    ]);
  });

  it('finds quadruplets for a non-zero target', () => {
    expect(fourSum([-1, 0, 1, 2, -1, -4], 1)).to.deep.equal([
      [-1, -1, 1, 2],
    ]);
  });

  it('deduplicates repeated values and keeps each quadruplet ordered', () => {
    expect(fourSum([2, 2, 2, 2, 2], 8)).to.deep.equal([[2, 2, 2, 2]]);
    expect(fourSum([-2, 0, 0, 2, 2], 0)).to.deep.equal([[-2, 0, 0, 2]]);
  });

  it('returns no result where no quadruplet exists', () => {
    expect(fourSum([1, 2, 3, 4], 50)).to.deep.equal([]);
    expect(fourSum([], 10)).to.deep.equal([]);
    expect(fourSum([1, 2, 3], 10)).to.deep.equal([]);
  });
});

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.