Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

3Sum

Find every unique triplet in an array that adds up to zero by sorting first and then running two pointers for each fixed number, in O(n²) time.

mediumPattern: Two Pointers

Updated Medium read: 6 min read

Approaches at a glance

ApproachTimeSpace
Brute force with a set of seen tripletsO(n³)O(n)
Sort, then two pointersO(n²)O(n)

The problem

Given an array of integers, return every set of three elements that adds up to zero. Each triplet must use three different positions in the array, and the result must not contain the same triplet twice, whatever order its numbers are in.

[-1, 0, 1, 2, -1, -4]   →  [[-1, -1, 2], [-1, 0, 1]]
[0, 1, 1]               →  []
[0, 0, 0, 0]            →  [[0, 0, 0]]

In the first example -1, 0 and 1 can be picked in two ways, because there are two -1s, but [-1, 0, 1] is listed once.

The space figures below do not count the list of triplets that is returned.

Approach 1: brute force

Try every combination of three positions. Sorting a copy first means each triplet always comes out in the same order, so a text key such as "-1,0,1" is enough to spot one that has been recorded already.

JavaScript

function threeSumBruteForce(numbers) {
  const sorted = [...numbers].sort((a, b) => a - b);
  const seen = new Set();
  const triplets = [];
 
  for (let i = 0; i < sorted.length; i++) {
    for (let j = i + 1; j < sorted.length; j++) {
      for (let k = j + 1; k < sorted.length; k++) {
        if (sorted[i] + sorted[j] + sorted[k] !== 0) continue;
        const key = `${sorted[i]},${sorted[j]},${sorted[k]}`;
        if (seen.has(key)) continue;
        seen.add(key);
        triplets.push([sorted[i], sorted[j], sorted[k]]);
      }
    }
  }
  return triplets;
}

Python

def three_sum_brute_force(numbers):
    ordered = sorted(numbers)
    seen = set()
    triplets = []
 
    for i in range(len(ordered)):
        for j in range(i + 1, len(ordered)):
            for k in range(j + 1, len(ordered)):
                triplet = (ordered[i], ordered[j], ordered[k])
                if sum(triplet) != 0 or triplet in seen:
                    continue
                seen.add(triplet)
                triplets.append(list(triplet))
    return triplets

Time O(n³): three nested loops. Space O(n) for the sorted copy, plus the set of keys.

Approach 2: sort, then two pointers

Fix the first number of the triplet. What is left is a smaller question: find two numbers to its right that add up to the negative of the fixed number. On a sorted array that is exactly Two Sum on a Sorted Array, which two pointers solves in one pass.

So the plan is:

  1. Sort a copy of the array.
  2. For each position i, put left just after i and right at the end.
  3. If the three numbers add up to less than zero, move left up. If more, move right down. If exactly zero, record the triplet and move both.

Duplicates are handled by skipping, not by a set. Because equal values sit next to each other after sorting, it is enough to skip a fixed number that equals the one before it, and to skip a left value that equals the one just used.

JavaScript

function threeSum(numbers) {
  const sorted = [...numbers].sort((a, b) => a - b);
  const triplets = [];
 
  for (let i = 0; i < sorted.length - 2; i++) {
    if (sorted[i] > 0) break;
    if (i > 0 && sorted[i] === sorted[i - 1]) continue;
 
    let left = i + 1;
    let right = sorted.length - 1;
 
    while (left < right) {
      const sum = sorted[i] + sorted[left] + sorted[right];
 
      if (sum < 0) {
        left++;
      } else if (sum > 0) {
        right--;
      } else {
        triplets.push([sorted[i], sorted[left], sorted[right]]);
        left++;
        right--;
        while (left < right && sorted[left] === sorted[left - 1]) left++;
      }
    }
  }
  return triplets;
}

Python

def three_sum(numbers):
    ordered = sorted(numbers)
    triplets = []
 
    for i in range(len(ordered) - 2):
        if ordered[i] > 0:
            break
        if i > 0 and ordered[i] == ordered[i - 1]:
            continue
 
        left = i + 1
        right = len(ordered) - 1
 
        while left < right:
            total = ordered[i] + ordered[left] + ordered[right]
 
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                triplets.append([ordered[i], ordered[left], ordered[right]])
                left += 1
                right -= 1
                while left < right and ordered[left] == ordered[left - 1]:
                    left += 1
    return triplets

The early break is a small saving: once the fixed number is positive, everything to its right is positive too, and three positive numbers cannot add up to zero.

Walkthrough

[-1, 0, 1, 2, -1, -4] sorted is [-4, -1, -1, 0, 1, 2]:

i (value) left (value) right (value) Sum Action
0 (-4) 1 (-1) 5 (2) -3 Too small. left moves up four times and never reaches zero
1 (-1) 2 (-1) 5 (2) 0 Record [-1, -1, 2], move both
1 (-1) 3 (0) 4 (1) 0 Record [-1, 0, 1], move both; pointers cross
2 (-1) Same value as the previous i: skip
3 (0) 4 (1) 5 (2) 3 Too large, move right; pointers meet

Time O(n²): sorting costs O(n log n), then each of the n fixed numbers gets one O(n) pass. Space O(n) for the sorted copy. Sorting the input in place would avoid the copy, at the price of changing the caller's array.

Why skipping duplicates is enough

There are two places a repeated triplet could come from.

  • The same fixed value twice. With i on the first -1, the inner loop finds every triplet that starts with -1. Starting again from the second -1 could only find a subset of those, so it is skipped. The check is sorted[i] === sorted[i - 1], comparing with the previous element, so the first copy is still used and [-1, -1, 2] is still found.
  • The same pair twice for one fixed value. After recording a triplet, left moves past every copy of the value it just used. Once left holds a new value, right must hold a new value too for the sum to be zero, so right needs no skip loop of its own.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(threeSum([-1, 0, 1, 2, -1, -4])); // [[-1, -1, 2], [-1, 0, 1]]
console.log(threeSum([0, 0, 0, 0])); // [[0, 0, 0]]

Python

print(three_sum([-1, 0, 1, 2, -1, -4]))  # [[-1, -1, 2], [-1, 0, 1]]
print(three_sum([0, 0, 0, 0]))  # [[0, 0, 0]]

The comment after each line is the result you should see.

Common mistakes

  • Forgetting the comparator when sorting. sort() with no argument compares numbers as text, so -1 lands after -4 only by luck and 10 lands before 2. Always pass (a, b) => a - b.
  • Skipping duplicates with sorted[i] === sorted[i + 1]. That skips the first copy rather than the later ones and loses triplets such as [-1, -1, 2].
  • Stopping at the first match. Unlike Two Sum, one fixed number can belong to several triplets, so keep going after recording one.
  • Using a hash set of triplets in the fast version. It works, but it hides an avoidable cost; skipping equal neighbours needs no extra memory.

Original problem: LeetCode 15: 3Sum