3Sum

mediumTwo Pointers63 stepsJava · Python · C++

Find all unique triplets that sum to zero. Sort the array, fix the first number nums[i], then solve Two Sum II on the rest with two pointers. Skip equal neighbours to avoid duplicate triplets.

▶ Watch the animated trace

Traced input: nums = [-1, 0, 1, 2, -1, -4] → [[-1, -1, 2], [-1, 0, 1]]. Original problem: neetcode.io/problems/three-integer-sum

Complexity

BestO(n²)

AverageO(n²)

WorstO(n²)

SpaceO(1)

Sorting is O(n log n); the pair search is O(n) for each i. Output space not counted.

Key idea

After sorting, each fixed nums[i] turns the problem into finding a pair summing to -nums[i].
Two pointers find that pair in O(n) because the array is sorted.
Skip nums[i] == nums[i-1] so each first value is used once.
After a hit, step both pointers past equal values so the same pair isn't added again.
If nums[i] > 0, nothing after it can sum to zero, so stop.

Common mistakes

Using a HashSet of lists to dedupe is slower and still needs sorted triplets.
Skipping duplicates of i with nums[i] == nums[i+1] drops valid triplets like [-1, -1, 2].
Forgetting to move both pointers after a match causes an infinite loop.

Solution

Java

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 (nums[i] > 0) {
            break;
        }
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        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 {
                res.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--;
            }
        }
    }
    return res;
}

Python

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

C++

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    for (int i = 0; i + 2 < (int)nums.size(); i++) {
        if (nums[i] > 0) {
            break;
        }
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        int l = i + 1, r = (int)nums.size() - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (sum < 0) l++;
            else if (sum > 0) r--;
            else {
                res.push_back({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 res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
All zeros Duplicate skipping keeps a single [0, 0, 0].	`nums = [0, 0, 0, 0]`	`[[0, 0, 0]]`
No triplet The only candidate sums to 2.	`nums = [0, 1, 1]`	`[]`
Fewer than three numbers The outer loop doesn't run.	`nums = [1, -1]`	`[]`
Many duplicates Both pointer skips are needed here.	`nums = [-2, 0, 0, 2, 2]`	`[[-2, 0, 2]]`
All positive Breaks immediately because nums[0] > 0.	`nums = [1, 2, 3]`	`[]`