Given an integer array nums, find all unique triplets [nums[i], nums[j], nums[k]] — where i, j, and k are three different indices — whose values add up to 0.
Two triplets count as the same if they hold the same three values, so your answer must not contain any triplet twice. The order of the triplets, and the order of the numbers inside each triplet, does not matter.
x, the other two must sum to -x — that's the classic Two Sum problem.Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] (-1) + 0 + 1 = 0 and (-1) + (-1) + 2 = 0. The two distinct triplets are [-1,0,1] and [-1,-1,2]; order does not matter.
Input: nums = [0,1,1] Output: [] The only possible triplet, 0 + 1 + 1, does not sum to 0.
Input: nums = [0,0,0] Output: [[0,0,0]] 0 + 0 + 0 = 0, giving the single triplet [0,0,0].
- 3 <= nums.length <= 3000 - -10^5 <= nums[i] <= 10^5
3Sum is the problem that turns Two Sum into a pattern. The move — fix one number, reduce to a smaller sum problem — is the whole kSum ladder, and the sorted two-pointer squeeze it introduces reappears in Container With Most Water, Trapping Rain Water, and 4Sum. The real skill it teaches is disciplined duplicate handling.
O(1) neighbour check.Given nums, return all unique triplets that sum to 0. Triplets are the same if they hold the same three values; order doesn't matter.
Worked example — nums = [-1, 0, 1, 2, -1, -4] → sorted [-4, -1, -1, 0, 1, 2]
anchor -4: pair for 4? none anchor -1: pair for 1? (0,1)✓ → [-1,0,1] ; (-1,2)✓ → [-1,-1,2] anchor 0: pair for 0? none new result: [[-1,-1,2], [-1,0,1]] ✓
“Do the three indices have to be distinct?”
Yes — three different positions, though their values may coincide (e.g. [0,0,0]).
“Is the target always 0?”
Here yes. For an arbitrary target the pair simply needs to sum to target - anchor.
“How are duplicate triplets handled?”
The output must be a set of distinct value-triplets — [0,0,0] appears once even with many zeros. Duplicate-skipping is the crux.
“Does order within a triplet matter?”
No — [-1,0,1] and [0,-1,1] are the same answer.
“Return the values or the indices?”
The values (as triplets), unlike Two Sum which returns indices.
“How large can the array be?”
Up to 3000. An O(n³) brute force (~10¹⁰) times out; sorting + two pointers is O(n²).
A couple of questions.
The three indices must be distinct, and I return distinct value-triplets summing to zero?
Order within a triplet doesn't matter?
I'll sort, fix each anchor, and two-pointer the rest — O(n²), skipping duplicates to keep triplets unique.
Freeze an anchor x; the remaining two must sum to -x. You already know how to find a pair for a target — so 3Sum is Two Sum wrapped in a loop over anchors. Recognising this reduction is the whole idea, and it generalizes straight up to kSum.
On a sorted array, a left/right pointer pair finds the needed sum in one linear scan — no hash set, O(1) space, O(n²) overall. Sorting also makes equal values adjacent, so skipping duplicates is a simple neighbour comparison instead of bookkeeping a seen-set.
Two sources of duplicates: repeated anchors and repeated pointer values. Skip an anchor equal to the previous one, and after recording a match, advance both pointers past any values equal to the ones just used. Miss either and the same triplet leaks out multiple times.
| Every triple | Fix one + hash | Sort + two pointers | |
|---|---|---|---|
| Idea | Test all i<j<k | Anchor, then Two Sum by hash | Anchor, then squeeze inward |
| Time | O(n³) | O(n²) | O(n²) |
| Space | O(1) | O(n) | O(1) |
The full code for all three is in the Approaches selector below.
Key takeaway
3Sum = fix an anchor, then Two Sum the rest. Sort first so a two-pointer squeeze finds each pair in O(n) (total O(n²), O(1) space) and duplicates become adjacent — then skip repeated anchors and repeated pointer values to keep every triplet unique. This fix-and-reduce move is the entire kSum ladder.