3Sum is the problem that teaches sort-then-two-pointers, and it is asked constantly. The algorithm is the easy half. The half that decides whether you pass is de-duplication — the problem wants unique triplets, the input has repeats, and there are two separate places a duplicate can sneak in.
The problem
Given an array of integers, find all unique triplets that sum to zero. The result must not contain duplicate triplets, though the same value may appear in several different ones.
Input: [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Note there are two -1s in the input and both answers use one. That is fine —
what is forbidden is returning [-1, 0, 1] twice.Why sorting is the whole idea
Brute force is three nested loops, O(n³), plus a hash set to squash duplicate
triplets afterwards. Sorting first buys three things at once, which is why it is worth the
O(n log n):
- Two pointers become possible. With the array in order, a sum that is too small can only be
fixed by moving the left pointer right, and one that is too large by moving the right pointer
left. That turns the inner
O(n²)intoO(n). - Duplicates become adjacent, so skipping them is a comparison with the neighbour rather than a hash set.
- Each triplet comes out already in ascending order, so
[-1, 0, 1]and[1, -1, 0]cannot both appear.
The shape is then: fix the leftmost element with an outer loop, and two-pointer the rest of the
array for a pair summing to its negation. This is Two
Sum run n times, on a sorted array where the two-pointer form applies.
The two places duplicates get in
This is the part to be deliberate about, because both are one line and both are easy to leave out.
The anchor. If nums[i] equals nums[i - 1], every
triplet starting at i was already found starting at i - 1. Skip it.
Compare backwards, not forwards — nums[i] == nums[i + 1] would skip the
first of a run, and [-1, -1, 2] needs that first one.
Inside the pair. After recording a hit, advance both pointers past their own
runs. Without this, [-2, 0, 0, 2, 2] reports [-2, 0, 2] twice: the pointers
step inward onto the second 0 and the second 2, which sum identically.
One more line is worth adding for a different reason. Once nums[i] > 0, the array
is sorted so the two elements after it are at least as large, and no triplet can reach zero —
break. It is not needed for correctness, it is a real speedup on positive-heavy input,
and it shows you are still thinking about the sorted invariant.
Java
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
if (nums[i] > 0) break; // sorted: nothing can reach 0
if (i > 0 && nums[i] == nums[i - 1]) continue; // same anchor as last round
int lo = i + 1, hi = n - 1;
while (lo < hi) {
int sum = nums[i] + nums[lo] + nums[hi];
if (sum < 0) {
lo++;
} else if (sum > 0) {
hi--;
} else {
result.add(List.of(nums[i], nums[lo], nums[hi]));
// Step both pointers past their own runs of equal values.
while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
lo++;
hi--;
}
}
}
return result;
}
}Both inner while loops keep the lo < hi guard. Dropping it lets the
pointers cross on an input like [0, 0, 0, 0] and read out of bounds.
Python
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
nums.sort()
result = []
n = len(nums)
for i in range(n - 2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
lo, hi = i + 1, n - 1
while lo < hi:
total = nums[i] + nums[lo] + nums[hi]
if total < 0:
lo += 1
elif total > 0:
hi -= 1
else:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo + 1]:
lo += 1
while lo < hi and nums[hi] == nums[hi - 1]:
hi -= 1
lo += 1
hi -= 1
return resultnums.sort() sorts the caller's list in place. If mutating the input is not
acceptable, use nums = sorted(nums) — and say which you are doing, because in a real
codebase silently reordering an argument is a bug waiting to happen. Java's
Arrays.sort(nums) has the same problem and no in-place-free alternative short of a
copy.
Complexity
O(n²) time: O(n log n) to sort, then an O(n) two-pointer
sweep for each of n anchors, and the sort vanishes into the square. Space is
O(1) beyond the output, plus whatever the sort uses — worth mentioning, since Java's
dual-pivot quicksort on primitives is O(log n) stack and Python's Timsort is
O(n).
The output itself can hold O(n²) triplets, so no solution can be better than that in
the worst case. There is no O(n log n) answer hiding here.
The family this belongs to
- 3Sum Closest (16) — same skeleton, but track the best
|sum - target|instead of testing for zero. No de-duplication needed at all, which makes it strictly easier. - 4Sum (18) — one more outer loop around the same two-pointer core,
O(n³), with the anchor-skip repeated at both levels. - 3Sum Smaller (259) — when
sum < target, every element between the pointers also works, so addhi - loat once rather than one at a time.
What the interviewer is checking
- That you sort first, and can say what sorting buys beyond "it feels tidier".
- Both de-duplication steps. Missing the anchor skip is the common failure; missing the
inner one shows up only on inputs like
[-2, 0, 0, 2, 2]. - That the anchor skip compares with
i - 1, noti + 1. [0, 0, 0, 0]— returns exactly one triplet, and does not run off the array.- That you reach for two pointers on a sorted array rather than a hash map. Both work; the two-pointer version uses no extra space and de-duplicates naturally.