12.3Sum

MediumBlind 75Two Pointers · 3/5

Problem

Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i, j, k are distinct indices and nums[i] + nums[j] + nums[k] == 0.

The result must not contain duplicate triplets (two triplets are duplicates if they hold the same values, regardless of which indices produced them). Order of triplets and of values inside a triplet does not matter.

Examples

Input:  nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation: (-1) + (-1) + 2 = 0 and (-1) + 0 + 1 = 0. The two -1s can form [-1, 0, 1] in two ways, but it is reported once.

Input:  nums = [0, 1, 1]
Output: []
Explanation: No triplet sums to zero.

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

Constraints

3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

💡 Key Insight

Sort first. Then fix the smallest element nums[i] and the problem reduces to Two Sum II on the sorted suffix: find nums[l] + nums[r] == -nums[i] with two pointers. Sorting also makes duplicates adjacent, so skipping equal neighbours (for i, and for l/r after a hit) removes duplicate triplets without any hash set. Total O(n²).

Brute Force

TimeO(n³)SpaceO(m)

Intuition

Try every triple of indices. To avoid duplicate value-triplets, sort the array first (so each triplet comes out in ascending order) and store results in a Set<List<Integer>>.

Algorithm

Sort nums.
For all i < j < k: if the sum is 0, add [nums[i], nums[j], nums[k]] to a set.
Return the set as a list.

Visualization

sorted = [-4, -1, -1, 0, 1, 2]

(-1, -1, 2) at (1,2,5) → add
(-1,  0, 1) at (1,3,4) → add
(-1,  0, 1) at (2,3,4) → already in set, ignored

Code

java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); // sorted triplets make equal value-sets identical lists
        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) {
                        found.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    }
                }
            }
        }
        return new ArrayList<>(found);
    }
}

Complexity

Time: O(n³) — every triple is checked.
Space: O(m) — m unique triplets in the set (plus sorting stack).

Hash Set per Pivot

TimeO(n²)SpaceO(n + m)

Intuition

Fix nums[i] and run the classic hash-set Two Sum on the rest: while scanning j, if -(nums[i] + nums[j]) was already seen after i, we have a triplet. Sorting plus a result set handles duplicates.

Algorithm

Sort nums.
For each i (skip if nums[i] == nums[i-1]):
- seen = new HashSet<>().
- For j = i+1..n-1: need = -nums[i] - nums[j]. If need is in seen, add [nums[i], need, nums[j]] to the result set. Add nums[j] to seen.
Return the result set as a list.

Visualization

sorted = [-4, -1, -1, 0, 1, 2]
i=1 (-1): nums[j]=-1 need 2 ✗ | nums[j]=0 need 1 ✗
          nums[j]=1  need 0 ✓ → [-1,0,1]
          nums[j]=2  need -1 ✓ → [-1,-1,2]
i=2 (-1): skipped (same as previous pivot)

Code

java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> found = new HashSet<>();
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue; // same pivot value gives the same triplets
            }
            Set<Integer> seen = new HashSet<>();
            for (int j = i + 1; j < n; j++) {
                int need = -nums[i] - nums[j];
                if (seen.contains(need)) {
                    // need <= nums[j] because it appeared earlier in sorted order
                    found.add(Arrays.asList(nums[i], need, nums[j]));
                }
                seen.add(nums[j]);
            }
        }
        return new ArrayList<>(found);
    }
}

Complexity

Time: O(n²) — n pivots, each with an O(n) hash scan.
Space: O(n + m) — the per-pivot seen set plus the result set.

Sort + Two PointersOptimal

TimeO(n²)SpaceO(1) extra besides the output (O(log n) for the sort's recursion).

Intuition

With the array sorted and pivot nums[i] fixed, the remaining pair must sum to -nums[i] inside nums[i+1..n-1] — exactly Two Sum II. Move l right when the sum is too small and r left when it is too big. After recording a triplet, advance l past all copies of its value so the same pair is not reported again. Skip repeated pivot values too. Since the array is sorted, once nums[i] > 0 no triplet can sum to zero, so we can stop early.

Algorithm

Sort nums.
For i = 0..n-3:
- If nums[i] > 0, break.
- If i > 0 and nums[i] == nums[i-1], continue.
- l = i + 1, r = n - 1. While l < r:
  - sum = nums[i] + nums[l] + nums[r].
  - sum < 0 → l++; sum > 0 → r--.
  - sum == 0 → record, l++, r--, then while l < r and nums[l] == nums[l-1], l++.
Return the list.

Dry Run

flowchart TD
    A["sorted = [-4,-1,-1,0,1,2]"] --> B["i=0, pivot -4<br/>needs pair sum 4: max is 1+2=3, no hit"]
    B --> C["i=1, pivot -1, l=2, r=5<br/>-1-1+2 = 0: record"]
    C --> D["l=3, r=4<br/>-1+0+1 = 0: record"]
    D --> E["l=4, r=3: stop"]
    E --> F["i=2, pivot -1 equals previous: skip"]
    F --> G["i=3, pivot 0, l=4, r=5<br/>0+1+2 = 3 too big, r=4: stop"]
    G --> H["result = [[-1,-1,2], [-1,0,1]]"]

Code

java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            if (nums[i] > 0) {
                break; // smallest value is positive: no more zero sums
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue; // skip duplicate pivots
            }
            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum < 0) {
                    l++;
                } else if (sum > 0) {
                    r--;
                } else {
                    result.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    l++;
                    r--;
                    while (l < r && nums[l] == nums[l - 1]) {
                        l++; // skip duplicate second values
                    }
                }
            }
        }
        return result;
    }
}

Complexity

Time: O(n²) — O(n log n) sort plus an O(n) two-pointer sweep for each of n pivots.
Space: O(1) extra besides the output (O(log n) for the sort's recursion).

Complexity Comparison

Approach	Time	Space
Brute Force	O(n³)	O(m)
Hash Set per Pivot	O(n²)	O(n + m)
Sort + Two Pointers	O(n²)	O(1) extra

Common Pitfalls

Skipping duplicates with nums[i] == nums[i + 1] instead of nums[i] == nums[i - 1] — this skips the first -1 in [-1, -1, 2] and loses that triplet.
Forgetting to skip duplicate l values after a hit, producing [-2, 0, 2] twice for [-2, 0, 0, 2, 2].
Stopping both pointers after a hit instead of moving them — an infinite loop.
Breaking on nums[i] >= 0 instead of > 0 misses [0, 0, 0].