LeetCode 15 · Two Pointers · concept: two-pointers
Problem
Return all unique triplets [a, b, c] in nums with a + b + c == 0. No duplicate triplets in the output.
nums = [-1, 0, 1, 2, -1, -4] -> [[-1, -1, 2], [-1, 0, 1]]
Approach 1 — brute force (all triples)
Three nested loops, dedupe with a set. O(n³) time — too slow, and the dedup is awkward.
Approach 2 — sort, then fix-one + two-pointer (optimal)
Reduce 3Sum to n runs of Two Sum II. Sort the array; then for each index i, look for two elements in the rest of the array summing to -nums[i], using the converging two-pointer sweep. Sorting is what enables both the two-pointer step and clean duplicate-skipping.
def threeSum(nums):
nums.sort()
res = []
for i in range(len(nums)):
if nums[i] > 0: # sorted: no way three ≥0 sum to 0
break
if i > 0 and nums[i] == nums[i - 1]:
continue # skip duplicate anchor
l, r = i + 1, len(nums) - 1
while l < r:
total = nums[i] + nums[l] + nums[r]
if total < 0:
l += 1
elif total > 0:
r -= 1
else:
res.append([nums[i], nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]: # skip duplicate seconds
l += 1
return resTime O(n²), space O(1) (ignoring output and sort). The outer loop is O(n), each two-pointer sweep is O(n).
The duplicate handling — the hard part
There are two independent dedup points, both relying on the sort:
- Anchor —
if i > 0 and nums[i] == nums[i-1]: continueskips a repeated first element, so you don’t emit the same triplet family twice. - Second element — after recording a hit,
while nums[l] == nums[l-1]: l += 1skips repeated middle values.
Sorting groups equal values adjacently, which is the only reason “skip if same as previous” works. Getting duplicates right — not the two-pointer sweep — is what makes 3Sum a step up from Two Sum II.
Complexity summary
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n³) | O(n) |
| Sort + two-pointer | O(n²) | O(1)* |
* excluding output.
Key insight
k-Sum reduces to (k−1)-Sum by fixing one element and recursing. 3Sum = “for each anchor, solve Two Sum II on the remainder.” The nums[i] > 0 early break and the two-tier duplicate skip are the details that separate a correct, efficient solution from a slow or buggy one. 4Sum is the same idea one level deeper (two nested anchors + two pointers).
Related
- concept: two-pointers, sorting
- builds on: Two Sum II
- prev: Two Sum II · next: Container With Most Water
Software engineering
Infrastructure & security
Computer science
Hardware & engineering