3Sum (LC 15)

Pattern: Sort + Two Pointers
Difficulty: Medium
Key Concept: Fix one element, then run sorted two-sum on the rest to find pairs that sum to the negative of the fixed value—total (O(n^2)) with deduplication.

Problem Statement

Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] such that:

• i != j, i != k, and j != k
• nums[i] + nums[j] + nums[k] == 0

The solution set must not contain duplicate triplets (same three values in any order counts once).

Input

• nums — integer array

Output

• List<List<Integer>> — all unique triplets summing to 0 (order of triplets and inner order may vary by implementation, but LeetCode accepts standard forms)

Example

• nums = [-1, 0, 1, 2, -1, -4] → [[-1, -1, 2], [-1, 0, 1]] (order may differ).

---

1. Algorithm & Pseudocode

Brute force

1. Sort a copy of the result candidates, or use a Set of normalized triplets later (simplest brute: triple nested loops + dedupe via set).
2. For each i from 0 to n - 3:
3. For each j from i + 1 to n - 2:
4. For each k from j + 1 to n - 1:
5. If nums[i] + nums[j] + nums[k] == 0, add triplet to a deduplication structure.
6. Convert deduped structure to list of lists and return.

Optimal

1. Sort nums ascending.
2. For each i from 0 to n - 3:
3. If i > 0 and nums[i] == nums[i - 1], skip i (avoid duplicate triplets for same first value).
4. Set left = i + 1, right = n - 1, need = -nums[i].
5. While left < right:
   • Let sum2 = nums[left] + nums[right].
   • If sum2 == need, record [nums[i], nums[left], nums[right]], then move left++ and right--, skipping any repeated nums[left] or nums[right] values.
   • Else if sum2 < need, left++.
   • Else right--.
6. Return collected triplets.

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why brute force is correct
You test every distinct triple of indices once; any valid triple is found. Deduplication handles repeated values.

Why brute force is slow
Three nested loops → (O(n^3)) time before dedupe overhead—too slow for (n) in the thousands.

Why sort first
Sorting lets you use two pointers for the inner pair search in (O(n)) per fixed i, and makes skipping duplicates easy by comparing neighbors.

Why fix i and solve two-sum
If nums[i] + nums[j] + nums[k] = 0, then nums[j] + nums[k] = -nums[i]. For a fixed i, you need pairs in the subarray to the right that sum to a constant need.

Why two pointers work on sorted tail
With left and right, if the pair sum is too small, increase it by moving left right; if too large, decrease by moving right left. This scans all candidate pairs for that i in linear time.

Why skip duplicate i
The same first value would produce the same set of solutions again.

Why skip duplicate left / right after a hit
You already recorded that combination; moving one step without skipping could yield the same nums[left] or nums[right] and duplicate triplets.

ASCII — shrinking window for fixed i

sorted nums: [ -4, -1, -1, 0, 1, 2 ]
              i=1 (-1)
                 L       R
need = 1
-1 + 2 = 1  → hit → record [-1,-1,2], advance L and R with skips

---

3. The Dry Run

Input: nums = [-1, 0, 1, 2, -1, -4]
After sort: [-4, -1, -1, 0, 1, 2]
Indices: 0 1 2 3 4 5

i	nums[i]	need	Window / action
0	-4	4	L=1,R=5: sums try toward 4 → (-1)+2=1 too small … eventually no hit
1	-1	1	L=2,R=5: -1+2=1 hit → [-1,-1,2]; advance L, R with skips
1 cont.	—	—	L=3,R=4: 0+1=1 hit → [-1,0,1]
2	-1	—	skip i (same as nums[1])
…	…	…	no new triplets

Result: [[-1,-1,2], [-1,0,1]] (list order may vary).

---

4. Java Solution

Brute Force

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) {
        int n = nums.length;
        Set<String> seen = new HashSet<>();
        List<List<Integer>> out = new ArrayList<>();
        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) {
                        int a = nums[i], b = nums[j], c = nums[k];
                        int x = Math.min(a, Math.min(b, c));
                        int z = Math.max(a, Math.max(b, c));
                        int y = a + b + c - x - z;
                        String key = x + "," + y + "," + z;
                        if (seen.add(key)) {
                            out.add(Arrays.asList(x, y, z));
                        }
                    }
                }
            }
        }
        return out;
    }
}

Time: (O(n^3)) plus hashing overhead.
Space: (O(k)) for dedupe keys, k = number of unique triplets found (worst case large).

Optimal

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

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int need = -nums[i];
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum2 = nums[left] + nums[right];
                if (sum2 == need) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                } else if (sum2 < need) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
    }
}

Time: (O(n^2)) — sort (O(n \log n)) plus (O(n)) two-pointer per i.
Space: (O(1)) extra besides output and sort stack (sort may use (O(\log n)) auxiliary).

---

5. The “Java vs. Others” Edge

• Arrays.sort(nums) sorts primitives in place efficiently; Collections.sort is for lists.
• Arrays.asList(a, b, c) builds a fixed-size list suitable for LeetCode’s expected type; for mutable triplets you could use new ArrayList<>(3) and add.
• Deduplication via index skipping avoids HashSet in the optimal solution—less allocation on the JVM.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	(O(n^3))	(O(k))~	Dedupe with encoded triplet keys.
Optimal	(O(n^2))	(O(\log n))~ to (O(1))	Sort + two pointers; ~sort auxiliary.