Skip to content
16-Week DSA Roadmap
LeetCode #15MediumProblem 4 of 8

3Sum

Find every different group of three numbers that adds up to zero, without listing the same group twice.

  • Sort first, then two pointers
  • Skipping duplicates

Before this, know: Two Sum II (two pointers on a sorted list), Sorting

The problem in plain English

You get a list nums. Find every group of three numbers (a triplet) that adds up to 0, using three different positions.

The catch: each group of values should appear only once in the answer, even if the list has repeated numbers that could build it in several ways.

Example: nums = [-1, 0, 1, 2, -1, -4].

nums
  1. -10
  2. 01
  3. 12
  4. 23
  5. -14
  6. -45
Two different triplets add up to 0: (-1) + (-1) + 2 and (-1) + 0 + 1. The answer is [[-1, -1, 2], [-1, 0, 1]].

The picture highlights -1, 0, 1 at positions 0, 1, 2. But -1, 0, 1 can also be built from positions 4, 1, 2 (the other -1). That’s the same group of values, so it must be listed once. The rules:

  • Return the values, not the positions.
  • No duplicate triplets. The order inside a triplet and the order of triplets don’t matter.
  • If nothing adds up to 0, return an empty list [].

Before you code: think it through

If we fix the first number a, we need two numbers b + c = −a. On a sorted list, that’s exactly Two Sum II. Sorting also does a second job: equal numbers end up next to each other, so repeats are easy to spot and skip.

  1. -40
  2. -11
  3. -12
  4. 03
  5. 14
  6. 25
Sorted: [-4, -1, -1, 0, 1, 2]. Fix i on -1, then we need two numbers to its right that add up to 1. Two pointers find them.

Pause and think

In the sorted list, we fixed i = 1 (value -1) and found [-1, -1, 2] and [-1, 0, 1]. Next, i = 2 is also -1. What would happen if we didn't skip it?

Approach 1: Brute force

Try every group of three positions i < j < k. When they add up to 0, sort the three values (so [0, -1, 1] and [-1, 0, 1] look the same) and store them in a set, a collection that keeps only one copy of each item, so repeats are dropped.

Brute force: every group of three

nums = [-1, 0, 1, 2, -1, -4]

nums
  1. -10
  2. 01
  3. 12
  4. 23
  5. -14
  6. -45
variables
sum
—
groups checked
0
result0 triplets
  • empty
  • i
  • j
  • k
  • Sums to 0
  • Sums to 0, but a repeat

Try every group of three positions i < j < k, and keep the groups that add up to 0. A set remembers which triplets we already have.

Step 1 / 22

Which line is running?

function threeSum(nums) {  const seen = new Set(); // triplets we already have, as text like "-1,0,1"  const result = [];Running now:   for (let i = 0; i < nums.length; i++) {    for (let j = i + 1; j < nums.length; j++) {      for (let k = j + 1; k < nums.length; k++) {        if (nums[i] + nums[j] + nums[k] === 0) {          const triplet = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);          const key = triplet.join(",");          if (!seen.has(key)) {            seen.add(key);            result.push(triplet);          }        }      }    }  }  return result;}

Brute force

function threeSum(nums) {  const seen = new Set(); // triplets we already have, as text like "-1,0,1"  const result = [];  for (let i = 0; i < nums.length; i++) {    for (let j = i + 1; j < nums.length; j++) {      for (let k = j + 1; k < nums.length; k++) {        if (nums[i] + nums[j] + nums[k] === 0) {          const triplet = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);          const key = triplet.join(",");          if (!seen.has(key)) {            seen.add(key);            result.push(triplet);          }        }      }    }  }  return result;}
def three_sum(nums):    seen = set()  # triplets we already have, as sorted tuples    result = []    for i in range(len(nums)):        for j in range(i + 1, len(nums)):            for k in range(j + 1, len(nums)):                if nums[i] + nums[j] + nums[k] == 0:                    triplet = tuple(sorted((nums[i], nums[j], nums[k])))                    if triplet not in seen:                        seen.add(triplet)                        result.append(list(triplet))    return result

Why is it slow?

Three loops inside each other. With 6 numbers there are 20 groups of three. With 3,000 numbers (LeetCode’s limit) there are about 3,000 × 2,999 × 2,998 ÷ 6 ≈ 4.5 billion. The work grows like n × n × n, written O(n³): double the list and the work goes up eight times.

The pattern: sort first, then two pointers

Pattern

Sort first, then two pointers

Template

Use it when: you need pairs or triplets with a target sum, the order of the input doesn't matter, and you must avoid duplicate answers.

Signal words

  • “triplets”
  • “sum to zero”
  • “all unique combinations”
  • “no duplicate triplets”
  • “return the values (not indexes)”

Approach 2: Sort, fix one, two pointers

  1. Sort nums from smallest to largest.
  2. For each index i (stopping two before the end, because we need two more numbers):
  3. If nums[i] > 0, stop: everything after it is positive too, so no sum can be 0.
  4. If nums[i] equals nums[i − 1], skip it (same first number as last time).
  5. Put left just after i and right on the last index. Add the three numbers.
  6. Too small: move left right. Too big: move right left.
  7. Exactly 0: save the triplet, move both pointers inward, then move left past any copies of the number it just used.

The first step shows the cells sliding into sorted order. After that, i (violet) is the fixed first number, and the shaded stretch is where left and right search. Watch the result list fill up on the right, and the faded cells being skipped as repeats.

Sort, fix one, two pointers

nums = [-1, 0, 1, 2, -1, -4]

nums (as given)
  1. -10
  2. 01
  3. 12
  4. 23
  5. -14
  6. -45
variables
nums[i]
—
pair must sum to
—
sum of three
—
result0 triplets
  • empty
  • Fixed first number (i)
  • left
  • right
  • Skipped repeat
  • Saved triplet

Here is the input, unsorted. Sorting it first lets us use two pointers, and puts equal numbers next to each other so repeats are easy to skip.

Step 1 / 23

Which line is running?

function threeSum(nums) {Running now:   nums.sort((a, b) => a - b); // smallest to largest  const result = [];  for (let i = 0; i < nums.length - 2; i++) {    if (nums[i] > 0) break; // three positive numbers can't add up to 0    if (i > 0 && nums[i] === nums[i - 1]) continue; // same first number: skip    let left = i + 1;    let right = nums.length - 1;    while (left < right) {      const sum = nums[i] + nums[left] + nums[right];      if (sum < 0) {        left++; // too small: we need a bigger number      } else if (sum > 0) {        right--; // too big: we need a smaller number      } else {        result.push([nums[i], nums[left], nums[right]]);        left++; // found one: move both pointers inward        right--;        while (left < right && nums[left] === nums[left - 1]) left++; // skip repeats      }    }  }  return result;}

Try all zeros [0, 0, 0, 0]: there are four ways to pick three zeros, but the duplicate skipping makes sure [0, 0, 0] appears once.

The code, line by line

Sort, fix one, two pointers

function threeSum(nums) {  nums.sort((a, b) => a - b); // smallest to largest  const result = [];  for (let i = 0; i < nums.length - 2; i++) {    if (nums[i] > 0) break; // three positive numbers can't add up to 0    if (i > 0 && nums[i] === nums[i - 1]) continue; // same first number: skip    let left = i + 1;    let right = nums.length - 1;    while (left < right) {      const sum = nums[i] + nums[left] + nums[right];      if (sum < 0) {        left++; // too small: we need a bigger number      } else if (sum > 0) {        right--; // too big: we need a smaller number      } else {        result.push([nums[i], nums[left], nums[right]]);        left++; // found one: move both pointers inward        right--;        while (left < right && nums[left] === nums[left - 1]) left++; // skip repeats      }    }  }  return result;}
def three_sum(nums):    nums.sort()  # smallest to largest    result = []    for i in range(len(nums) - 2):        if nums[i] > 0:            break  # three positive numbers can't add up to 0        if i > 0 and nums[i] == nums[i - 1]:            continue  # same first number as last time: skip        left, right = i + 1, len(nums) - 1        while left < right:            total = nums[i] + nums[left] + nums[right]            if total < 0:                left += 1  # too small: we need a bigger number            elif total > 0:                right -= 1  # too big: we need a smaller number            else:                result.append([nums[i], nums[left], nums[right]])                left += 1  # found one: move both pointers inward                right -= 1                while left < right and nums[left] == nums[left - 1]:                    left += 1  # skip repeats    return result

On LeetCode it’s var threeSum = function(nums) in JavaScript, and def threeSum(self, nums) inside class Solution in Python.

  • Line 2: sort. In JavaScript, sort compares items as text unless you give it (a, b) => a - b, which compares them as numbers. (Without it, -1 would come before -4, and 10 before 9.) Python’s sort() already sorts numbers properly.
  • Line 3: the list of triplets we’ll return.
  • Line 4: each i is the fixed first number. We stop two before the end so there is room for left and right.
  • Line 5 (JS) / lines 5–6 (Python): an early stop. In a sorted list, if the smallest of the three is positive, all three are, and they can’t make 0.
  • Line 6 (JS) / lines 7–8 (Python): skip a first number equal to the previous one. continue jumps to the next i. The i > 0 part avoids looking at nums[-1] on the very first round.
  • Lines 7–8 (JS) / line 9 (Python): the two pointers for the rest of the list.
  • Lines 9–14 (JS) / lines 10–15 (Python): this is Two Sum II. Too small, move left; too big, move right.
  • Line 16 (JS) / line 17 (Python): a hit. Save the three values.
  • Lines 17–18 (JS) / lines 18–19 (Python): move both pointers. If only left moved, right would need the same partner it just had.
  • Line 19 (JS) / lines 20–21 (Python): skip copies of the left number we just used, or we’d build the same triplet again.
  • The last line: return all the triplets.

Dry run

Sorted list: [-4, -1, -1, 0, 1, 2].

inums[i]leftrightsumwhat happens
0-415-4 + -1 + 2 = -3too small: left++
0-425-4 + -1 + 2 = -3too small: left++
0-435-4 + 0 + 2 = -2too small: left++
0-445-4 + 1 + 2 = -1too small: left++, pointers meet
1-125-1 + -1 + 2 = 0save [-1, -1, 2], move both
1-134-1 + 0 + 1 = 0save [-1, 0, 1], move both, pointers cross
2-1same as nums[1]: skip
30450 + 1 + 2 = 3too big: right--, pointers meet
nums sorted = [-4, -1, -1, 0, 1, 2]

The i = 2 row is where the duplicate skip earns its keep: without it, i = 2 would find [-1, 0, 1] a second time.

Complexity

Brute force

Time

O(n³)

Every group of three positions: about n × n × n ÷ 6 groups.

Space

O(n²)

The set remembers every triplet found. Any two numbers fix the third, so in the worst case there are about n × n of them.

Sort, fix one, two pointers

Time

O(n²)

Sorting is O(n log n). Then for each of the n choices of i, the two pointers walk at most n steps: n × n. For 3,000 numbers that's about 9 million steps instead of 4.5 billion.

Space

O(1)

Only i, left and right, plus whatever memory the sort uses (O(log n) to O(n) depending on the language). The answer list isn't counted.

O(n log n) is a new one: “n times the number of times you can halve n”. It’s a little more than O(n) and a lot less than O(n²). It’s how fast good sorting algorithms are, and here it’s swamped by the O(n²) loops anyway.

Common mistakes and edge cases

What to say out loud:

  1. “Brute force is three loops, O(n³), with a set to drop repeats.”
  2. “If I sort, fixing one number turns the rest into Two Sum II on a sorted list.”
  3. “Sorting also puts equal values side by side, so I can skip duplicates without a set.”
  4. “Total O(n²) time, O(1) extra space apart from sorting.”
  5. Walk the duplicate skips on [-1, -1, 0, 1] before you code.

Likely follow-up questions:

  • “Why not a hash set inside, like Two Sum?” That also works in O(n²), but removing duplicates is messier and it uses O(n) extra space.
  • “What about 4Sum?” Add one more outer loop: O(n³). The same sort-and-skip ideas apply.
  • “Closest sum to a target instead of exactly 0?” That’s 3Sum Closest: keep the best sum seen, and move pointers the same way.

Related problems: