3Sum

Problem Overview

Given an array of integers, find all unique triplets that sum to zero. Each triplet's values are returned in ascending order, and the result must not contain duplicate triplets.

Why solve this?

Extends the two-pointer pair-sum idea to three numbers by fixing one position at a time and running the sorted two-pointer sweep on the rest — while introducing the real challenge of this family of problems: cleanly skipping duplicates.

Pattern Recognition

Whenever a problem asks for combinations of k numbers summing to a target and duplicates must be eliminated, sort first — sorting turns duplicate detection into a simple 'skip if equal to the previous value' check, and reduces the problem to (k-1)-sum on the remaining pointers.

Prerequisites

• Pair with Given Sum in Sorted Array — the two-pointer sweep this problem repeats once per fixed index.
• Two Sum.
• Comfort with sorting as a preprocessing step.

Hints

1. Sort the array first — this turns 'find three numbers summing to zero' into 'fix one number, then find two numbers summing to its negation' using the Pair Sum technique.
2. After sorting, skip a fixed index if it holds the same value as the previous index — this avoids picking the same starting number twice and producing duplicate triplets.
3. After finding a valid triplet, skip past any following duplicate values for both the left and right pointers before continuing the sweep.

Approach

Sort the array first. Then iterate a fixed index i from left to right, skipping it if nums[i] equals the previous element (to avoid choosing the same starting value twice, which would produce duplicate triplets). For each fixed i, run a Pair-with-Given-Sum-style two-pointer sweep over the remaining subarray (i+1 to end) looking for two values that sum to -nums[i]. Whenever a matching pair is found, record the triplet, then advance both pointers inward past any further duplicate values before continuing the sweep. Because the array is sorted throughout, every triplet is naturally emitted with its values in ascending order, and the duplicate-skipping keeps the result free of repeated triplets without needing a set for deduplication.

Code

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; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            if (nums[i] > 0) break;
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
}

Related Problems

• Reverse an Arrayeasy
• Second Largest Element in an Arrayeasy
• Plus Oneeasy
• Running Sum of 1d Arrayeasy