← DSA Atlas
Dedicated problem page · #15

3Sum

MediumTwo PointersSorted two-pointer scan around a fixed anchorTwo pointers (after sorting)
Solve on LeetCode ↗
15
MediumTwo PointersTwo pointers (after sorting)Sorted two-pointer scan around a fixed anchor

3Sum

Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] with distinct indices i, j, k such that nums[i] + nums[j] + nums[k] == 0. The result must not contain duplicate triplets.

Open official problem prompt ↗
In plain English

Enumerate every distinct set of three values in the array that add up to exactly zero, without listing the same set twice.

Picture it like this

Think of a sorted bookshelf: you pin one book, then use a left hand and a right hand at the two ends of the remaining shelf, sliding them inward until their prices plus the pinned book balance a budget of zero.

Example
Input
nums = [-1, 0, 1, 2, -1, -4]
Output
[[-1, -1, 2], [-1, 0, 1]]
Why
(-1)+(-1)+2 = 0 and (-1)+0+1 = 0; every other combination fails to sum to zero or is a duplicate.
Constraints
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5
Pattern lesson

See the pattern, then code

Sorted two-pointer scan around a fixed anchor
Recognition clue

You must find combinations that hit a fixed sum (0) and the order of elements does not matter, so sorting plus a two-pointer sweep is far cheaper than trying every triple.

↗
Two Pointers

Sorted input, opposite-end scanning, pair search, or in-place compaction.. Sort first; then fix the smallest element of the triplet and reduce the rest to a 2Sum-on-a-sorted-array problem, moving two pointers inward based on whether the current sum is too small or too large.

New words, made simpleKnow these before the algorithm
Anchor
The fixed first element i of the triplet that the two pointers search around.
Two-pointer convergence
Two indices starting at opposite ends that move toward each other, exploiting sorted order.
Duplicate skip
Advancing past equal neighboring values so the same triplet is not emitted more than once.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute-force triple loop

Cubic time is far too slow for n up to 3000 and dedup bookkeeping is awkward.

Try every combination of three indices and keep those summing to zero, deduplicating with a set.

Time O(n^3)Space O(n)
Best choiceSort + fix anchor + two pointers

Sorting enables monotonic pointer moves and easy deduplication, giving the optimal quadratic solution.

Sort, fix each i, and solve the remaining 2Sum with converging pointers, skipping duplicates in place.

Time O(n^2)Space O(1)
The rule we keep true

Invariant

For a fixed anchor i, every zero-sum pair in nums[i+1:] lies between lo and hi; moving lo/hi never discards a still-possible pair because the array is sorted.

Why this is correct

Reasoning

In sorted order, if the current sum is too small the only way to grow it is to raise the left value, and if too large the only way to shrink it is to lower the right value; so each move safely eliminates exactly one impossible option, and skipping equal values prevents duplicate triplets.

The algorithm in three movesSay these aloud before coding
1Sort nums so pointers can move monotonically

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

2Fix each index i as the first element, skipping duplicate values

i=1 (val -1), lo=2, hi=5 -> sum 0 -> [-1,-1,2]

3Set lo = i+1 and hi = n-1 and scan toward each other

i=1 continues, lo=3, hi=4 -> sum 0 -> [-1,0,1]

4Move lo up when the sum is negative, hi down when positive, record and skip duplicates when it is zero

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
-40
-11
-12
03
14
25
1 · Read[-1,0,1,2,-1,-4]
2 · AskWhat order lets pointers move monotonically?
3 · Update state[-4,-1,-1,0,1,2]
4 · ResultArray sorted ascending.
Key takeaway

After sorting, anchor -1 at index 1 pairs with lo=-1 and hi=2 to make the first zero-sum triplet.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 2-3Sort and set up

    Sorting is what makes the two-pointer moves and duplicate skips valid.

  2. 2
    Lines 6-10Anchor loop with pruning

    Break once nums[i] > 0 (no way to reach zero) and skip duplicate anchors.

  3. 3
    Lines 11-16Converging pointers

    Shift lo/hi based on the sign of the running total to hunt the target of -nums[i].

  4. 4
    Lines 17-23Record and dedup

    On a hit, store the triplet then walk both pointers past equal values to avoid repeats.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Fewer than 3 elements yields an empty list
  • All zeros gives a single [0,0,0]
  • No triplet sums to zero returns []
  • Many repeated values must not produce duplicate triplets
!

Common beginner mistakes

  • Forgetting to skip duplicate anchors or duplicate pointer values, producing repeated triplets
  • Using a set of tuples instead of in-place skips, which works but wastes memory
  • Not breaking when nums[i] > 0, doing needless work
Check your understanding

Why is it safe to move lo forward when the total is negative rather than moving hi?

More in Two Pointers

#11Container With Most WaterConverging pointers on a width-vs-height tradeoff#184SumTwo fixed anchors plus a sorted two-pointer inner scan#26Remove Duplicates from Sorted ArraySlow/fast in-place overwrite#31Next PermutationFind pivot, swap successor, reverse suffix#42Trapping Rain WaterConverging pointers tracking left/right maxima#75Sort ColorsDutch National Flag partition