Problem 6.5 · Two PointersMedium

3Sum

PatternTwo Pointers: Opposite Ends Hash Map Lookup (Complement)

What it teaches: Sort, fix one element, two-pointer the rest, and skip duplicates at every level: O(n³) becomes O(n²).

Practise it on judges as “3Sum”.

The problem

Given an integer array nums, return all unique triplets [a, b, c] from different positions with a + b + c = 0. No duplicate triplets.

Example 1

Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]

Example 2

Input: nums = [0, 1, 1]
Output: []

Example 3

Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]

Constraints

3 ≤ nums.length ≤ 3000
−10⁵ ≤ nums[i] ≤ 10⁵

Pattern clues in the wording

→ Triples with a target sum
→ Values, not indexes, are returned (sorting is allowed)
→ "Unique" → sort and skip duplicates
→ n ≤ 3000 → O(n²) is fine

These clues point to Two Pointers: Opposite Ends: Start one pointer at each end and move them towards each other, using a rule to decide which one moves.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> out = new ArrayList<>();
        return out;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [-1,0,1,2,-1,-4]	[[-1,-1,2],[-1,0,1]]
2	nums = [0,1,1]	[]
3	nums = [0,0,0]	[[0,0,0]]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Brute force: every triple · O(n³)2. Optimal: sort + fix one + two pointers · O(n²)

Brute force: every triple

Time O(n³) Space O(number of triples)

Check all triples and store sorted triples in a set to remove duplicates.

Approach 1

import java.util.*;

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

Verdict: 4.5 × 10⁹ triples at n = 3000: too slow.

Optimal: sort + fix one + two pointers

Time O(n²) Space O(1) extra besides the output (sorting aside)

Sort. For each i (skipping values equal to the previous i), run two pointers on i+1..n−1 looking for −nums[i]. On a match, record it, then move L and R past all copies of their values.

If nums[i] > 0, stop: three values that are all at least nums[i] can't sum to 0.

▶ Dry run: Fixing −1 and closing insorted nums = [-4, -1, -1, 0, 1, 2]

-4

↑i

-1

↑L

-1

↑R

Step 1/5Fix −4: need L + R = 4. The largest pair is 1 + 2 = 3, so nothing works.

Approach 2

import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> out = new ArrayList<>();
        for (int i = 0; i < nums.length - 2 && nums[i] <= 0; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;       // skip duplicate first values
            int L = i + 1, R = nums.length - 1;
            while (L < R) {
                int sum = nums[i] + nums[L] + nums[R];
                if (sum < 0) L++;
                else if (sum > 0) R--;
                else {
                    out.add(List.of(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--;
                }
            }
        }
        return out;
    }
}

Verdict: n outer steps × O(n) two-pointer scan.

Before you submit

Edge cases and common mistakes

Test these inputs

All zeros
No triplet
Many duplicates
Exactly three elements

Mistakes people make

Forgetting to skip duplicate i values.
Skipping duplicates before recording the triplet.
Returning indexes instead of values.

Interview

Follow-up questions

How would you solve 4Sum?

What about the triplet closest to a target?

Command Palette