{ }SolveLogs
⌕
Home / Two Pointers / #15
LeetCode #15 Medium

3Sum

3Sum is LeetCode 15 (Medium). You get an integer array nums and must return every unique triplet of values that adds up to exactly zero.

  • The three values must come from three different positions i, j and k; one element cannot be used twice.
  • Each triplet is reported once. Two triplets holding the same three values, in any order, count as the same answer.
  • The triplets, and the values inside each one, may be returned in any order.
  • If no three values sum to zero, return an empty list.

The array holds 3 to 3,000 numbers, each between −10⁵ and 10⁵. At 3,000 elements, checking every triple is about 4.5 billion sums, far too slow; an O(n²) scan is about 9 million steps.

Constraints
  • 3 <= nums.length <= 3000
  • -10⁵ <= nums[i] <= 10⁵
arraytwo-pointerssorting
Open on LeetCode ↗
02

Intuition

Trying every triple is O(n³). 3Sum drops to O(n²) by turning it into many small Two Sum problems on a sorted array. Fix the first number, and the other two must add up to its negative.

On a sorted array that pair is found with two pointers from the ends: a sum that is too small can only grow by moving the left pointer, and one that is too big can only shrink by moving the right. Each fixed number costs one O(n) sweep.

Sorting also handles uniqueness. Equal values sit next to each other, so skipping repeats means each triplet is produced exactly once.

How to spot this pattern

"Find k numbers with a target sum" on an unsorted array: sort it, fix k − 2 numbers with loops, and finish with a two-pointer scan. 3Sum Closest (16) keeps the same scan and tracks the nearest sum; 4Sum (18) adds one more fixed loop for O(n³).

03

Approach

Try it first

Before reading on, sort [-1, 0, 1, 2, -1, -4] and run the two pointers by hand for i = 1. Then say which lines stop [-1, 0, 1] from being reported twice.

Two ways to solve it

Sort + two pointersBest
Time O(n²)Space O(1) extra

Sort, fix each nums[i], then move left and right inward to find pairs that sum to -nums[i].

  • Speed: one linear pass per i, so O(n²) in total.
  • Duplicates: skipped in place, no set needed.
  • Space: only the pointers, besides the output and sort.

This is the standard interview answer.

Solution & demo ↓
Brute force with a set
Time O(n³)Space O(number of triplets)

Try every i < j < k, and when the three values sum to 0, sort them and add them to a set.

  • Duplicates: the set keeps one copy of each sorted triplet.
  • Scale: with n up to 3000 that is about 4.5 billion checks, too slow.
  • Use: a simple checker for small tests.

Correct, but it times out on LeetCode.

Code ↓

Sorting lets two pointers replace the third loop, cutting O(n³) to O(n²) and removing the need for a set. The steps, code and live demo below follow two pointers, and the brute-force code is further down.

1

Sort the array

O(n log n). After sorting, pointer moves change the sum in a known direction, and duplicates are adjacent. In the 3Sum Python code nums.sort() sorts the list in place, so no copy is made.

2

Fix the first number

Loop i from 0 to n − 3:

  • nums[i] > 0 – break. It is the smallest of the three, so no sum can be 0.
  • nums[i] == nums[i − 1] – skip. Every triplet starting with this value was already found.
3

Close in with two pointers

Set L = i + 1, R = n − 1, and while L < R compute total:

  • total < 0 – move L right (need a bigger value).
  • total > 0 – move R left (need a smaller value).
  • total == 0 – record the triplet, move both pointers in, then move L past any value equal to the one just used.
4

Why no triplet is missed

When the sum is too small, nums[L] paired with the largest remaining value still falls short, so nums[L] pairs with nothing in the window and can be discarded. The same argument discards nums[R] when the sum is too big. Every move removes only values that cannot be part of an answer.

04

3Sum solution in Python | C++ | Java

▶1class Solution:
▶2 def threeSum(self, nums: List[int]) -> List[List[int]]:
▶3 nums.sort()
▶4 result = []
▶5 for i in range(len(nums) - 2):
▶6 if nums[i] > 0:
▶7 break
▶8 if i > 0 and nums[i] == nums[i - 1]:
▶9 continue
▶10 left, right = i + 1, len(nums) - 1
▶11 while left < right:
▶12 total = nums[i] + nums[left] + nums[right]
▶13 if total < 0:
▶14 left += 1
▶15 elif total > 0:
▶16 right -= 1
▶17 else:
▶18 result.append([nums[i], nums[left], nums[right]])
▶19 left += 1
▶20 right -= 1
▶21 while left < right and nums[left] == nums[left - 1]:
▶22 left += 1
▶23 return result
nums-40-11-12031425input-1012-1-4foundnone yet
nums[-4, -1, -1, 0, 1, 2]sorted
Sort the array. Two things follow from sorted order: moving a pointer right always makes the sum bigger and moving one left makes it smaller, and equal values sit next to each other, so duplicates can be skipped by comparing neighbours.
nums-40i-11L-12031425Rcheck-4i+-1L+2R=-3sumtoo small: L rightfoundnone yet
i, L, R0, 1, 5
sum-3too small
Fix nums[i] = -4; now find two numbers after it that sum to 4, with L and R at both ends of the rest. The sum is -3, too small. R is already the largest value left, so no pair with this L can work: nums[L] = -1 is ruled out. Move L right to a bigger value.
nums-40i-11-12L031425Rcheck-4i+-1L+2R=-3sumtoo small: L rightfoundnone yet
i, L, R0, 2, 5
sum-3too small
The sum is -3, too small. R is already the largest value left, so no pair with this L can work: nums[L] = -1 is ruled out. Move L right to a bigger value.
nums-40i-11-1203L1425Rcheck-4i+0L+2R=-2sumtoo small: L rightfoundnone yet
i, L, R0, 3, 5
sum-2too small
The sum is -2, too small. R is already the largest value left, so no pair with this L can work: nums[L] = 0 is ruled out. Move L right to a bigger value.
nums-40i-11-120314L25Rcheck-4i+1L+2R=-1sumtoo small: L rightfoundnone yet
i, L, R0, 4, 5
sum-1too small
The sum is -1, too small. R is already the largest value left, so no pair with this L can work: nums[L] = 1 is ruled out. Move L right to a bigger value.
nums-40-11i-12L031425Rcheck-1i+-1L+2R=0sumzero: record itfound-1-12
triplet[-1, -1, 2]
found1
Fix nums[i] = -1; now find two numbers after it that sum to 1, with L and R at both ends of the rest. Sum is 0. Record [-1, -1, 2]. Both pointers now move inward: keeping either one would need the other to hold the same value, which would only repeat this triplet.
nums-40-11i-1203L14R25check-1i+0L+1R=0sumzero: record itfound-1-12-101
triplet[-1, 0, 1]
found2
Sum is 0. Record [-1, 0, 1]. Both pointers now move inward: keeping either one would need the other to hold the same value, which would only repeat this triplet.
nums-40-11-12i031425check-1i − 1=-1isame first number: skipfound-1-12-101
i2same value as i − 1
Skip a repeated first number. i = 1 already used -1 as the first number and found every triplet that starts with it. Running again would find the same triplets again.
nums-40-11-1203i14L25Rcheck0i+1L+2R=3sumtoo big: R leftfound-1-12-101
i, L, R3, 4, 5
sum3too big
Fix nums[i] = 0; now find two numbers after it that sum to 0, with L and R at both ends of the rest. The sum is 3, too big. L is already the smallest value left, so nums[R] = 2 cannot be in any triplet with this i. Move R left to a smaller value.
nums-40-11-12031425checkreturn 2 unique tripletsfound-1-12-101
result[-1,-1,2] [-1,0,1]
Done. Each i ran one two-pointer pass, O(n) each, so the whole search is O(n²). Skipping repeated values at i and at L is what makes every triplet in the result unique, without any hash set.
05

Brute force with a set

Three nested loops try every triple of indices. Each zero-sum triple is sorted before it goes into the set, so [-1, 0, 1] and [0, -1, 1] count once.

▶1class Solution:
▶2 def threeSum(self, nums: List[int]) -> List[List[int]]:
▶3 n = len(nums)
▶4 seen = set()
▶5 for i in range(n):
▶6 for j in range(i + 1, n):
▶7 for k in range(j + 1, n):
▶8 if nums[i] + nums[j] + nums[k] == 0:
▶9 seen.add(tuple(sorted((nums[i], nums[j], nums[k]))))
▶10 return [list(t) for t in seen]
06

Common pitfalls

Skipping duplicates by looking ahead at i

✗ Wrong
if nums[i] == nums[i + 1]:
    continue
✓ Right
if i > 0 and nums[i] == nums[i - 1]:
    continue

Looking ahead skips the first copy, so [-1, -1, 2] is never found: by the time i reaches the second -1, the other -1 is behind it. Compare with the previous value instead.

Stopping after the first match for an i

✗ Wrong
else:
    result.append([nums[i], nums[left], nums[right]])
    break
✓ Right
else:
    result.append([nums[i], nums[left], nums[right]])
    left += 1
    right -= 1

One i can have several partners: with i = -4 in [-4, 0, 1, 3, 4] both [−4, 0, 4] and [−4, 1, 3] are answers.

Breaking on zero instead of only on positives

✗ Wrong
if nums[i] >= 0:
    break
✓ Right
if nums[i] > 0:
    break

With nums[i] == 0 the triplet [0, 0, 0] is still possible. Breaking on >= 0 returns [] for [0, 0, 0] instead of [[0, 0, 0]].

07

Edge cases

All zeros, e.g. [0, 0, 0, 0]

One triplet [0, 0, 0]. The skip at i and at L stops it from being added three times.

Many duplicates, e.g. [-2, 0, 0, 2, 2]

Only [-2, 0, 2]. The second 0 is skipped at L; the extra 2 is passed over because the sum no longer matches.

08

Complexity

Time
O(n²)
Space
O(1) extra
This 3Sum LeetCode solution sorts in O(n log n); the outer loop runs n times and each two-pointer pass is O(n), so O(n²) dominates. Extra space is O(1) besides the output, or O(log n) to O(n) for the sort, depending on the language.
09

3Sum FAQ

Can 3Sum be solved faster than O(n²)?

Not in general. O(n²) is the best known for comparison-based 3Sum, and the "3SUM conjecture" in complexity theory assumes no algorithm is meaningfully faster. For interviews, O(n²) is the expected optimum.

What is the difference between Two Sum and 3Sum?

Two Sum returns indices of one pair and uses a hash map in O(n). 3Sum returns values of all unique triplets, so it sorts and runs a two-pointer Two Sum for each fixed first number, O(n²).

← Prev · #14
Longest Common Prefix
Next · #16 →
3Sum Closest