Problem statement

Given an integer array nums, return all unique triplets [a, b, c] with a + b + c = 0 (using three different indices).

Each triplet must be sorted in ascending order, and the list of triplets sorted lexicographically.

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

• 0 <= nums.length <= 20
• -25 <= nums[i] <= 25

Hints for 3Sum

1. Hint 1

   Sort first — that makes both deduplication and ordering natural.

2. Hint 2

   Fix the smallest element, then two-pointer the remainder for the pair summing to its negation.

How to solve 3Sum

Sorting first turns a three-way search into a one-way scan plus a two-pointer sweep, and — just as usefully — makes duplicates adjacent so they can be skipped cheaply. Fix the smallest element of the triplet, then look for a pair in the remaining suffix summing to its negation.

Approach

1. Sort the array.
2. Fix index i as the first element. Skip it if it equals the previous value — that triplet family was already produced.
3. Set l = i + 1 and r = n - 1.
4. While l < r, look at nums[i] + nums[l] + nums[r]: too small means move l right, too big means move r left.
5. On an exact zero, record the triplet, then move both pointers inward past any duplicate values before continuing.

Why it works

The two-pointer sweep is correct because the array is sorted: moving l right can only increase the sum and moving r left can only decrease it, so each comparison eliminates a whole family of pairs that cannot work — no pair is ever skipped wrongly. Deduplication is exact because equal values sit together after sorting, so skipping repeats at each of the three positions guarantees every distinct triplet appears once. The output is also lexicographically sorted for free, since i and then l both advance through non-decreasing values.

Complexity

• Time — O(n^2)
• Space — O(n)

Pitfalls

• Three dedup points are needed — on i, on l, and on r. Missing any one produces repeated triplets.
• After recording a hit, advance both pointers; moving only one re-finds the same triplet.
• Skip duplicates of i by comparing with nums[i - 1], not nums[i + 1].
• Arrays shorter than three elements simply produce nothing — the loops must handle that without indexing errors.

Reference solution

Python

from typing import List

def threeSum(nums: List[int]) -> List[List[int]]:
    s = sorted(nums)
    out = []
    for i in range(len(s) - 2):
        if i > 0 and s[i] == s[i - 1]:
            continue
        l, r = i + 1, len(s) - 1
        while l < r:
            total = s[i] + s[l] + s[r]
            if total == 0:
                out.append([s[i], s[l], s[r]])
                while l < r and s[l] == s[l + 1]:
                    l += 1
                while l < r and s[r] == s[r - 1]:
                    r -= 1
                l += 1
                r -= 1
            elif total < 0:
                l += 1
            else:
                r -= 1
    return out

Java

public static int[][] threeSum(int[] nums) {
    int[] s = nums.clone();
    Arrays.sort(s);
    List<int[]> out = new ArrayList<>();
    int n = s.length;
    for (int i = 0; i + 2 < n; i++) {
        if (i > 0 && s[i] == s[i - 1]) continue;
        int l = i + 1, r = n - 1;
        while (l < r) {
            int sum = s[i] + s[l] + s[r];
            if (sum < 0) l++;
            else if (sum > 0) r--;
            else {
                out.add(new int[]{s[i], s[l], s[r]});
                l++;
                r--;
                while (l < r && s[l] == s[l - 1]) l++;
                while (l < r && s[r] == s[r + 1]) r--;
            }
        }
    }
    return out.toArray(new int[0][]);
}

C++

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<int> s = nums;
    sort(s.begin(), s.end());
    vector<vector<int>> out;
    int n = (int) s.size();
    for (int i = 0; i + 2 < n; i++) {
        if (i > 0 && s[i] == s[i - 1]) continue;
        int l = i + 1, r = n - 1;
        while (l < r) {
            int sum = s[i] + s[l] + s[r];
            if (sum < 0) l++;
            else if (sum > 0) r--;
            else {
                out.push_back(vector<int>{s[i], s[l], s[r]});
                l++;
                r--;
                while (l < r && s[l] == s[l - 1]) l++;
                while (l < r && s[r] == s[r + 1]) r--;
            }
        }
    }
    return out;
}

JavaScript

var threeSum = function(nums) {
    const s = nums.slice().sort(function(a, b) { return a - b; });
    const out = [];
    for (let i = 0; i < s.length - 2; i++) {
        if (i > 0 && s[i] === s[i - 1]) continue;
        let l = i + 1, r = s.length - 1;
        while (l < r) {
            const sum = s[i] + s[l] + s[r];
            if (sum === 0) {
                out.push([s[i], s[l], s[r]]);
                while (l < r && s[l] === s[l + 1]) l++;
                while (l < r && s[r] === s[r - 1]) r--;
                l++;
                r--;
            } else if (sum < 0) {
                l++;
            } else {
                r--;
            }
        }
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium