3Sum: Every Zero-Sum Triplet, Without Duplicates

Given an integer array nums, return every triplet [a, b, c] of values from distinct positions such that a + b + c = 0. Each triplet must be sorted in non-decreasing order, no two triplets may be equal, and the list of triplets must itself be in non-decreasing order.

Examples

Input	Output	Why
`nums = [-1, 0, 1, 2, -1, -4]`	`[[-1, -1, 2], [-1, 0, 1]]`	The value −1 appears twice, so it may be used twice — but the triplet [-1, 0, 1] may only be reported once.
`nums = [1, 2, 3]`	`[]`	Nothing sums to zero.
`nums = [0, 0, 0, 0]`	`[[0, 0, 0]]`	One triplet, not four.

Constraints

3 ≤ n ≤ 3000
−10⁵ ≤ nums[i] ≤ 10⁵
Positions are distinct; values need not be

Hints

Hint 1

The brute force is three nested loops, O(n³). Before optimising, ask what sorting would buy you.

Hint 2

Fix the first value. What is left is: find two values in the remaining suffix that sum to a known target — the previous problem.

Hint 3

Duplicates are the whole difficulty. Once a value has been used as the fixed element, skip past every copy of it. Do the same for both pointers after recording a hit.

Dry run on `[-1,0,1,2,-1,-4]`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 12

Step 1 / 12

sorted
-40-11-12031425
n6
Sorted first: [-4, -1, -1, 0, 1, 2]. Equal values are now adjacent, which is what makes the duplicate rules cheap.
Step 2 / 12

sorted
-40i-11lo-12031425hi
fixed-4want4
Fix nums[0] = -4. Now find two values in the rest that sum to 4.
Step 3 / 12

sorted
-40i-11lo-12031425hi
sum1want4
-1 + 2 = 1 < 4. nums[1] is too small to pair with anything left; move lo right.
Step 4 / 12

sorted
-40i-11-12lo031425hi
sum1want4
-1 + 2 = 1 < 4. nums[2] is too small to pair with anything left; move lo right.
Step 5 / 12

sorted
-40i-11-1203lo1425hi
sum2want4
0 + 2 = 2 < 4. nums[3] is too small to pair with anything left; move lo right.
Step 6 / 12

sorted
-40i-11-120314lo25hi
sum3want4
1 + 2 = 3 < 4. nums[4] is too small to pair with anything left; move lo right.
Step 7 / 12

sorted
-40-11i-12lo031425hi
fixed-1want1
Fix nums[1] = -1. Now find two values in the rest that sum to 1.
Step 8 / 12

sorted
-40-11i-12lo031425hi
fixed-1want1
-1 + 2 = 1. Triplet [-1, -1, 2]. Now skip past every copy of both values.
Step 9 / 12

sorted
-40-11i-1203lo14hi25
fixed-1want1
0 + 1 = 1. Triplet [-1, 0, 1]. Now skip past every copy of both values.
Step 10 / 12

sorted
-40-11-12i031425
fixed-1
nums[2] = -1 repeats the previous fixed value. Every triplet starting here was already found. Skip.
Step 11 / 12

sorted
-40-11-1203i14lo25hi
fixed0want0
Fix nums[3] = 0. Now find two values in the rest that sum to 0.
Step 12 / 12

sorted
-40-11-1203i14lo25hi
sum3want0
1 + 2 = 3 > 0. nums[5] is too large; move hi left.

How to think about it

This is the problem usually listed as 3Sum.

Sorting costs O(n log n), which you pay once and recover many times over. After it, two facts hold that did not before: equal values sit next to each other, and the pair scan from the previous problem works on any suffix.

So: walk i from left to right, and for each i look for two values in nums[i+1..] that sum to −nums[i]. That inner search is the two-pointer scan, O(n), which makes the whole thing O(n²).

Three places need a duplicate guard, and candidates routinely miss the third:

The fixed element. If nums[i] == nums[i-1], every triplet starting at i was already found at i-1. Skip.
After a hit, the left pointer. Advance past every copy of the value just used.
After a hit, the right pointer. Same, from the other side. Skipping only one of the two still emits duplicates.

One early exit is worth having: once nums[i] > 0 the three smallest remaining values are all positive, so no triplet can sum to zero. Stop.

Complexity. Time O(n²) · Space O(1) beyond the sort

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def three_sum(nums):
    nums = sorted(nums)
    n, out = len(nums), []
    for i in range(n - 2):
        if nums[i] > 0:                      # everything left is positive
            break
        if i > 0 and nums[i] == nums[i - 1]: # this fixed value is already done
            continue
        lo, hi, want = i + 1, n - 1, -nums[i]
        while lo < hi:
            total = nums[lo] + nums[hi]
            if total == want:
                out.append([nums[i], nums[lo], nums[hi]])
                left, right = nums[lo], nums[hi]
                while lo < hi and nums[lo] == left:
                    lo += 1                  # skip duplicates on both sides,
                while lo < hi and nums[hi] == right:
                    hi -= 1                  # or the same triplet comes back
            elif total < want:
                lo += 1
            else:
                hi -= 1
    return out

#include <vector>
#include <algorithm>

std::vector<std::vector<int>> solve(std::vector<int> nums) {
    std::sort(nums.begin(), nums.end());
    const int n = static_cast<int>(nums.size());
    std::vector<std::vector<int>> out;
    for (int i = 0; i + 2 < n; ++i) {
        if (nums[i] > 0) break;                          // everything left is positive
        if (i > 0 && nums[i] == nums[i - 1]) continue;   // fixed value already done
        int lo = i + 1, hi = n - 1;
        const long long want = -static_cast<long long>(nums[i]);
        while (lo < hi) {
            const long long total = static_cast<long long>(nums[lo]) + nums[hi];
            if (total == want) {
                out.push_back({nums[i], nums[lo], nums[hi]});
                const int left = nums[lo], right = nums[hi];
                while (lo < hi && nums[lo] == left) ++lo;     // both sides
                while (lo < hi && nums[hi] == right) --hi;
            } else if (total < want) {
                ++lo;
            } else {
                --hi;
            }
        }
    }
    return out;
}

import java.util.*;

class Solution {
    public int[][] threeSum(int[] input) {
        int[] nums = input.clone();
        Arrays.sort(nums);
        List<int[]> out = new ArrayList<>();
        for (int i = 0; i + 2 < nums.length; i++) {
            if (nums[i] > 0) break;                          // everything left is positive
            if (i > 0 && nums[i] == nums[i - 1]) continue;   // fixed value already done
            int lo = i + 1, hi = nums.length - 1;
            long want = -(long) nums[i];
            while (lo < hi) {
                long total = (long) nums[lo] + nums[hi];
                if (total == want) {
                    out.add(new int[]{nums[i], nums[lo], nums[hi]});
                    int left = nums[lo], right = nums[hi];
                    while (lo < hi && nums[lo] == left) lo++;     // both sides
                    while (lo < hi && nums[hi] == right) hi--;
                } else if (total < want) {
                    lo++;
                } else {
                    hi--;
                }
            }
        }
        return out.toArray(new int[0][]);
    }
}

function threeSum(nums) {
  const a = [...nums].sort((x, y) => x - y);
  const out = [];
  for (let i = 0; i < a.length - 2; i++) {
    if (a[i] > 0) break;                        // everything left is positive
    if (i > 0 && a[i] === a[i - 1]) continue;   // fixed value already done
    let lo = i + 1, hi = a.length - 1;
    const want = -a[i];
    while (lo < hi) {
      const total = a[lo] + a[hi];
      if (total === want) {
        out.push([a[i], a[lo], a[hi]]);
        const left = a[lo], right = a[hi];
        while (lo < hi && a[lo] === left) lo++;   // skip duplicates on both
        while (lo < hi && a[hi] === right) hi--;  // sides, not just one
      } else if (total < want) lo++;
      else hi--;
    }
  }
  return out;
}

fn solve(input: &[i64]) -> Vec<(i64, i64, i64)> {
    let mut nums = input.to_vec();
    nums.sort_unstable();
    let n = nums.len();
    let mut out = Vec::new();
    for i in 0..n.saturating_sub(2) {
        if nums[i] > 0 { break; }                              // everything left is positive
        if i > 0 && nums[i] == nums[i - 1] { continue; }       // fixed value already done
        let (mut lo, mut hi) = (i + 1, n - 1);
        let want = -nums[i];
        while lo < hi {
            let total = nums[lo] + nums[hi];
            match total.cmp(&want) {
                std::cmp::Ordering::Equal => {
                    out.push((nums[i], nums[lo], nums[hi]));
                    let (left, right) = (nums[lo], nums[hi]);
                    while lo < hi && nums[lo] == left { lo += 1; }    // both sides
                    while lo < hi && nums[hi] == right { hi -= 1; }
                }
                std::cmp::Ordering::Less => lo += 1,
                std::cmp::Ordering::Greater => hi -= 1,
            }
        }
    }
    out
}

import Data.List (sort)

-- Fix the head of the sorted list, then scan the tail from both ends.
solve :: [Int] -> [(Int, Int, Int)]
solve xs = go (sort xs)
  where
    go (a : rest@(_ : _ : _))
      | a > 0     = []                       -- everything left is positive
      | otherwise = scan a rest ++ go' a rest
    go _ = []

    -- skip every further copy of the fixed value
    go' a rest = go (dropWhile (== a) rest)

    scan a rest = walk 0 (n - 1)
      where
        v = rest
        n = length v
        at i = v !! i
        walk lo hi
          | lo >= hi        = []
          | total == want   = (a, at lo, at hi) : walk (skipL lo) (skipR hi)
          | total <  want   = walk (lo + 1) hi
          | otherwise       = walk lo (hi - 1)
          where
            total = at lo + at hi
            want  = negate a
            skipL i = let x = at i in until (\j -> j >= hi || at j /= x) (+ 1) i
            skipR i = let x = at i in until (\j -> j <= lo || at j /= x) (subtract 1) i

Where people lose marks

De-duplicating by pushing every triplet into a hash set. It works, and it tells the interviewer you did not want to reason about the ordering. It also costs memory proportional to the output.
Skipping duplicates before recording the hit rather than after. You lose the legitimate triplet [0, 0, 0].
Using i < n rather than i < n - 2 as the outer bound, then indexing off the end.
Forgetting that the same value may be reused when it appears at two positions, as in [-1, -1, 2].

Variants to try

Triplets summing to an arbitrary target rather than zero: the same code with the target shifted.
Four numbers summing to a target: fix two and run the scan, O(n³). Beyond that, meet in the middle.
The triplet whose sum is closest to a target: same scan, but track the best difference rather than an exact hit.
What if you only need the count of triplets, not the triplets themselves? The duplicate handling changes completely.

Next problems

Easy10 min

Pair with a given sum in a sorted array

The cleanest example of the two-pointer idea: sorted input, one pass, no extra memory.

Open the problem → Medium15 min

Two walls holding the most water

The input is not sorted, but one comparison still rules out an end for good: the shorter wall can never do better.

Open the problem →

All distinct triplets summing to zero

Examples

Constraints

Hints

Dry run on `[-1,0,1,2,-1,-4]`

How to think about it

The solution, in six languages

Where people lose marks

Variants to try

Next problems

Pair with a given sum in a sorted array

Two walls holding the most water

Keep going

Pair with a given sum in a sorted array

Two walls holding the most water

The pattern behind it

All distinct triplets summing to zero

Examples

Constraints

Hints

Dry run on [-1,0,1,2,-1,-4]

How to think about it

The solution, in six languages

Where people lose marks

Variants to try

Next problems

Pair with a given sum in a sorted array

Two walls holding the most water

Keep going

Pair with a given sum in a sorted array

Two walls holding the most water

The pattern behind it

Dry run on `[-1,0,1,2,-1,-4]`