3Sum in JavaScript: Two Pointers After Sorting

Following on from a previous article where I discussed using a two‑pointer method to solve the Valid Palindrome Problem in JavaScript/TypeScript, I wanted to share another common LeetCode problem that can also be solved using the two‑pointers technique: the 3Sum Problem.

The 3Sum Problem

The 3Sum problem involves finding all unique triplets in an array that sum up to zero. Each triplet should not contain any duplicate elements.

For example, given the array [‑1, 0, 1, 2, ‑1, ‑4], the solution would be [[‑1, ‑1, 2], [‑1, 0, 1]].

To solve this, we can use a combination of sorting the array and employing a two‑pointer approach along with additional logic. Just like last time, I'll also show you some fairly basic Jest tests to add coverage to the function and make sure it works as expected.

Approach

To solve this problem the steps look something like this:

1. Sort the array in ascending order to simplify the process of finding unique triplets.
2. Fix one element (from experience, it is easiest if this is at index i) and use two pointers (left and right) to find the other two elements whose sum is equal to the negative of the fixed element (e.g., ‑nums[i]).
3. If the sum of elements at nums[i], nums[left], and nums[right] is less than zero, we move the left pointer to the right to increase the sum.
4. If the sum is greater than zero, move the right pointer to the left to decrease the sum.
5. If the sum is equal to zero, record the triplet and move both pointers to find other possible solutions.
6. To avoid duplicates, skip elements with the same value at nums[i], nums[left], and nums[right].

Implementation

As is always the case with development, there are any number of different ways of structuring this function, but here's my version ‑ following the steps from above:

const threeSum = (nums: number[]): number[][] => {  const result: number[][] = [];  nums.sort((a, b) => a - b);  for (let i = 0; i < nums.length - 2; i++) {    if (i === 0 || (i > 0 && nums[i] !== nums[i - 1])) {      let left = i + 1;      let right = nums.length - 1;      const target = -nums[i];      while (left < right) {        if (nums[left] + nums[right] === target) {          result.push([nums[i], nums[left], nums[right]]);          while (left < right && nums[left] === nums[left + 1]) left++;          while (left < right && nums[right] === nums[right - 1]) right--;          left++;          right--;        } else if (nums[left] + nums[right] < target) {          left++;        } else {          right--;        }      }    }  }  return result;}

No doubt that with time and patience, this code could be improved upon to increase performance, but for the sake of this article, it does exactly what we need it to do.

Add Some Tests

Given that we have some examples that we know are valid, we really should add some coverage to our function to make sure that it behaves as expected and correctly:

import { threeSum } from './threesum';describe('3Sum', () => {  it('should find all unique triplets that sum up to zero', () => {    expect(threeSum([-1, 0, 1, 2, -1, -4])).toEqual([      [-1, -1, 2],      [-1, 0, 1],    ]);    expect(threeSum([0, 0, 0, 0])).toEqual([[0, 0, 0]]);    expect(threeSum([-2, 0, 0, 2, 2])).toEqual([[-2, 0, 2]]);  });  it('should handle empty and small arrays', () => {    expect(threeSum([])).toEqual([]);    expect(threeSum([1])).toEqual([]);    expect(threeSum([1, 2])).toEqual([]);  });});

Wrapping‑Up

The 3Sum Problem is another example of how to use the two‑pointer pattern (in this case: alongside some simple array sorting). This combination is a powerful tool for solving more real‑world problems (rather than just a LeetCode exercise).