ProblemMediumLeetCode #157 min read

3Sum

Find all unique triplets summing to zero. Sort + two-pointers, with deduping.

arraystwo-pointerssorting

Intro

Given an array, return all unique triplets that sum to zero. The brute force is O(n³); sort + two pointers brings it to O(n²) with no extra hashing.

Key insight

Fix one element, then run a 2-sum on the remaining sorted suffix. Skip duplicates at every level.

Approach

1Sort the array.
2For each i, set target = -a[i] and run two pointers l = i+1, r = n-1.
3On a hit, advance both pointers and skip duplicates.
4On too-small / too-large, advance the appropriate pointer.
5Skip i if a[i] == a[i-1] to avoid duplicate triplets.

Complexity

Time

O(n²)

Space

O(1) extra (ignoring output)

Code

Snippetjava

List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> ans = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int l = i + 1, r = nums.length - 1, t = -nums[i];
        while (l < r) {
            int s = nums[l] + nums[r];
            if (s == t) {
                ans.add(Arrays.asList(nums[i], nums[l], nums[r]));
                while (l < r && nums[l] == nums[l + 1]) l++;
                while (l < r && nums[r] == nums[r - 1]) r--;
                l++; r--;
            } else if (s < t) l++; else r--;
        }
    }
    return ans;
}

Pitfalls

Forgetting the dedupe at each level — produces repeated answers.
Stopping the outer loop too early (i must reach n - 2).

Variants & follow-ups

3Sum Closest (LC 16)
4Sum (LC 18)