3Sum

Sort, fix i, then two-pointer scan

time O(n²)space O(1)

Brute force checks every triple in O(n³). Instead, sort once: now duplicates sit next to each other and, with one element i fixed, the remaining pair-search becomes sorted Two Sum — a single comparison tells you which pointer to move. n fixed positions × one linear scan each = O(n²).

Details

Animated on: Find all unique triplets in [-1, 0, 1, 2, -1, -4] that sum to 0.

Problem:3SumMedium

Pattern:Two Pointers

Sort, fix i, then two-pointer scan

step 1 / 11

-1

[0]

[1]

[2]

[3]

-1

[4]

-4

[5]

Input [-1, 0, 1, 2, -1, -4], target sum 0. Unsorted, we can't steer a pointer or spot the duplicate -1s. Sort first.

Pseudocode

1FUNCTION threeSum(nums):
2  sort nums into ascending order
3  FOR i from 0 to (length of nums) - 3:
4    IF i > 0 and nums[i] equals nums[i-1]: skip to the next i
5    set l to i+1, r to (length of nums) - 1
6    WHILE l < r:
7      s = nums[i] + nums[l] + nums[r]
8      IF s equals 0: save this triple, move l one step right and r one step left
9      ELSE IF s < 0: move l one step right, otherwise move r one step left
10  RETURN the saved triples

← / → step · space play · Home restart

Every step in words

Show all 11 steps

Input [-1, 0, 1, 2, -1, -4], target sum 0. Unsorted, we can't steer a pointer or spot the duplicate -1s. Sort first.
Sorted: [-4, -1, -1, 0, 1, 2]. Fix i on -4; l and r bracket everything to its right. s = -4 + (-1) + 2 = -3.
-3 < 0: too small, and r already holds the largest value 2 — only l can raise the sum. l moves right onto the duplicate -1: s = -4 + (-1) + 2 = -3 again.
l keeps sliding: -4 + 0 + 2 = -2, then -4 + 1 + 2 = -1 — even the two biggest partners can't lift -4 to 0. l meets r; no triple contains -4.
Advance i to -1 and reset l, r around it. s = -1 + (-1) + 2 = 0 — a hit on the very first pair.
Record [-1, -1, 2]. Move BOTH pointers: with i fixed, keeping l and shrinking only r makes the sum negative, keeping r and growing only l makes it positive — no other zero pair reuses either end.
l = 0, r = 1 now. s = -1 + 0 + 1 = 0 — a second zero triple with the same fixed i.
Record [-1, 0, 1]. l++ and r-- make the pointers cross — every pair right of i = -1 has been judged. Inner scan done.
i advances to index 2 — but nums[2] = -1 equals nums[1]. Scanning it would only re-find [-1, 0, 1]. Skip duplicate fixed values; this is what keeps the output UNIQUE.
Fix i on 0. s = 0 + 1 + 2 = 3 > 0: too big, and l already holds the smallest partner — only r can shrink the sum. r moves left, meets l, and the scan for i = 0 ends empty.
i = 4 would leave only one element to its right — no pair, so the loop stops at n-3. Answer: [[-1, -1, 2], [-1, 0, 1]]. Sorting bought us duplicate-skipping AND the O(n) pair scan per fixed i.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve 3Sum in the editor All Arrays problems Back to roadmap