3Sum

MediumTwo Pointers · Sort + Fix One🧩 Two Pointers LeetCode #15 ↗Updated Oct 30, 2026

Problem

Given an integer array nums, list every distinct triplet of values [a, b, c], taken from three different positions, with a + b + c = 0. Two triplets with the same values (in any order) count once. The output order does not matter.

Input[-1,0,1,2,-1,-4]Output[[-1,-1,2],[-1,0,1]]

Input[0,1,1]Output[]

Input[0,0,0]Output[[0,0,0]]

3 ≤ n ≤ 3000 · -10⁵ ≤ nums[i] ≤ 10⁵ · no duplicate triplets

Try it yourself

Java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Sort, then fix the first value nums[i]: the rest is Two Sum II on the sorted suffix with target -nums[i]. Sorting also makes duplicates adjacent, so they are skipped with simple neighbour checks.

PatternTwo Pointers

Instinct Sorted input, a pair/triple hitting a target, or something symmetric? Put one pointer at each end and move the one that can only improve things.

Memory hack Squeeze from both ends - every step throws away a whole row of the brute-force grid.

Open the Two Pointers guide →

Approaches

Brute ForceAll Triplets + Set of Sorted Triplets

Time O(n³)Space O(n²)

Check every index triple i < j < k. To drop duplicates, sort each matching triplet and store it in a HashSet (at most O(n²) distinct triplets exist, since two values fix the third).

Java

public List<List<Integer>> threeSum(int[] nums) {
    Set<List<Integer>> triplets = new HashSet<>();
    int n = nums.length;
    for (int i = 0; i < n - 2; i++)
        for (int j = i + 1; j < n - 1; j++)
            for (int k = j + 1; k < n; k++)
                if (nums[i] + nums[j] + nums[k] == 0) {
                    List<Integer> t = Arrays.asList(nums[i], nums[j], nums[k]);
                    Collections.sort(t);
                    triplets.add(t);
                }
    return new ArrayList<>(triplets);
}

Correct but cubic: ~4.5·10⁹ checks at n = 3000.

BetterSort + HashSet Two Sum per `i`

Time O(n²)Space O(n)

Sort, fix nums[i] (skipping repeated values of i), then scan j to the right with a seen set: if -nums[i]-nums[j] was seen, we have a triplet. After a hit, skip equal nums[j] so the same pair isn't reported twice.

Java

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        Set<Integer> seen = new HashSet<>();
        for (int j = i + 1; j < nums.length; j++) {
            int need = -nums[i] - nums[j];
            if (seen.contains(need)) {
                res.add(Arrays.asList(nums[i], need, nums[j]));
                while (j + 1 < nums.length && nums[j] == nums[j + 1]) j++;
            }
            seen.add(nums[j]);
        }
    }
    return res;
}

Quadratic, but hashing costs extra memory and constant factor.

OptimalSort + Two Pointers

Time O(n²)Space O(log n)

Sort, fix nums[i], and run two pointers l = i+1, r = n-1: sum < 0 → l++, sum > 0 → r--. On a hit, record it and step both pointers past equal values. If nums[i] > 0, no later triplet can reach 0 — stop. (Space excludes the output; O(log n) is the sort's stack.)

Java

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < nums.length - 2 && nums[i] <= 0; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // same first value
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum < 0) left++;
            else if (sum > 0) right--;
            else {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            }
        }
    }
    return result;
}

Dry runsorted: [-4,-1,-1,0,1,2]

i il leftr right changed

i=0
-4
i
-1
l
-1

0

1

2
r
-3 < 0 → l++ (to l=r)
i=1
-4

-1
i
-1
l
0

1

2
r
0 → add [-1,-1,2]
i=1
-4

-1
i
-1

0
l
1
r
2

0 → add [-1,0,1]
i=2
-4

-1

-1
i
0

1

2

dup of i=1 → skip
i=3
-4

-1

-1

0
i
1
l
2
r
3 > 0 → r-- → done ✔

Same O(n²) bound, no hashing, natural de-duplication — the standard answer.

At a glance

Level	Approach	Time	Space
Brute Force	All Triplets + Set of Sorted Triplets	`O(n³)`	`O(n²)`
Better	Sort + HashSet Two Sum per `i`	`O(n²)`	`O(n)`
Optimal	Sort + Two Pointers	`O(n²)`	`O(log n)`

Common pitfalls

Forgetting to skip duplicate nums[i] — emits [-1,0,1] twice.
Skipping duplicates before recording a hit loses [-1,-1,2].
Missing left < right in the skip loops — index out of bounds.

Interview tips

Say it out loud: “3Sum = sort + loop + Two Sum II”.
O(n²) is the accepted bound; sorting's O(n log n) is dominated.
Generalise: kSum recurses down to the same two-pointer core.

Pattern

Sort + fix one + two pointers → k-sum style problems that need unique combinations.

My notes saved in this browser