3Sum

Difficulty: Medium
Topics: Array, Two Pointers, Sorting
Link: https://leetcode.com/problems/3sum/

Problem Description

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:


Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:


Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:


Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

Solution

1. Problem Deconstruction

Technical Restatement
Given an array nums of integers, return all unique triplets [a,b,c] where:

∃ distinct indices i,j,k such that a = nums[i], b = nums[j], c = nums[k]
$a + b + c = 0$
No two triplets in the output are permutations of each other

Beginner Explanation
Find all unique groups of three different numbers from the list that add to zero. Even if the same numbers appear in different orders or positions, they count as the same group and should only be listed once.

Mathematical Formulation
Let $S = \{ (a,b,c) \mid a = nums[i], b = nums[j], c = nums[k], i \neq j \neq k \}$
Find $T \subseteq S$ where:

$\forall t \in T, \sum t = 0$
$\forall t_1, t_2 \in T, t_1 \neq t_2 \Rightarrow t_1$ is not a permutation of $t_2$

Constraint Analysis

3 ≤ nums.length ≤ 3000:
- Brute-force $O(n^3)$ (≈27 billion operations at n=3000) is impossible. Requires ≤ $O(n^2)$
- Edge Case: Minimal input like [0,0,0] must be handled
-10⁵ ≤ nums[i] ≤ 10⁵:
- Negative numbers require careful pointer management in two-sum approaches
- Zero-heavy arrays need duplicate checks

2. Intuition Scaffolding

Real-World Metaphor
Imagine a balance scale where you need to place three weights (could be negative) to perfectly balance both sides. You’re searching through a warehouse of weights, but can’t reuse the same physical weight (index) twice, even if multiple identical weights exist.

Gaming Analogy
In a RPG crafting system, combine three reagents where their “magic values” cancel out (sum to 0). Each reagent can only be used once from your inventory slots (indices), but you might have duplicate items.

Math Analogy
This is equivalent to finding all 3-element subsets of a multiset that form a linear combination $x + y + z = 0$ , modulo permutation equivalence classes.

Common Pitfalls

Naive Duplicate Checking: Using a hash set to store sorted triplets → $O(n^3)$ space (explodes with large n)
Skipping Too Early: Failing to handle multiple duplicate values after finding a valid triplet
Overlooking Negative Jumps: In two-pointer approach, not accounting for negative values when adjusting pointers
Index Collisions: Not ensuring i < j < k during iteration leading to repeated work
Sorting Neglect: Attempting to solve without sorting, making duplicate elimination intractable

3. Approach Encyclopedia

Brute Force (Theoretical)

result = set()
for i in 0..n-3:
    for j in i+1..n-2:
        for k in j+1..n-1:
            if nums[i]+nums[j]+nums[k] == 0:
                result.add(sorted([nums[i],nums[j],nums[k]]))
return list(result)

Time: $O(n^3)$ → Prohibitive for n=3000
Space: $O(n^3)$ (for hash set storage)

Hash Map Optimization

Sort the array
For each i, use a hash map to find pairs (j,k) where nums[j] + nums[k] = -nums[i]

nums.sort()
result = []
for i in range(len(nums)-2):
    if i > 0 and nums[i] == nums[i-1]: continue
    target = -nums[i]
    seen = set()
    for j in range(i+1, len(nums)):
        complement = target - nums[j]
        if complement in seen:
            result.append([nums[i], complement, nums[j]])
            while j+1 < len(nums) and nums[j] == nums[j+1]: j +=1
        seen.add(nums[j])
return result

Time: $O(n^2)$ but with hash overhead
Space: $O(n)$ for the hash map

Optimal Two-Pointer Approach

nums.sort()
result = []
for i in range(len(nums)-2):
    if i > 0 and nums[i] == nums[i-1]: continue  # Skip duplicates
    left, right = i+1, len(nums)-1
    while left < right:
        total = nums[i] + nums[left] + nums[right]
        if total < 0:
            left +=1
        elif total > 0:
            right -=1
        else:
            result.append([nums[i], nums[left], nums[right]])
            # Skip duplicates for left and right
            while left < right and nums[left] == nums[left+1]: left +=1
            while left < right and nums[right] == nums[right-1]: right -=1
            left +=1
            right -=1
return result

Time: $O(n^2)$ → Sorting ( $O(n \log n)$ ) dominated by nested loops
Space: $O(1)$ (ignoring sorting memory)

Visualization

Sorted Array: [-4, -1, -1, 0, 1, 2]
i=0 (-4)
  left=1 (-1), right=5 (2) → sum=-3 → too low → move left
i=1 (-1)
  left=2 (-1), right=5 (2) → sum=0 → record [-1,-1,2]
  left=3 (0), right=4 (1) → sum=0 → record [-1,0,1]

4. Code Deep Dive

Optimal Solution Code

def threeSum(nums):
    nums.sort()
    res = []
    for i in range(len(nums)-2):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        l, r = i+1, len(nums)-1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0:
                l +=1
            elif s > 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

Line-by-Line Analysis

nums.sort(): Enables pointer logic and duplicate skipping
for i in range(len(nums)-2): Ensures at least 3 elements remain
if i > 0 and nums[i] == nums[i-1]: Skips duplicate i values
l, r = i+1, len(nums)-1: Two pointers for 2-sum search
s = ...: Current triplet sum
s < 0 → l +=1: Sum too small → increase left
s > 0 → r -=1: Sum too large → decrease right
else → append: Valid triplet found
while l < r ... l +=1: Skip duplicate left values
l +=1; r -=1: Move pointers inward after recording

Edge Case Handling

All Zeros (Ex3): i=0 triggers append, then l and r collapse
Duplicates (Ex1): nums[i] == nums[i-1] skips repeated -1
No Solution (Ex2): Loop exits without appending

5. Complexity War Room

Hardware Considerations

At n=3000:
- Sorting ≈3000 log 3000 ≈ 30,000 operations
- Nested loops: (3000) * 3000 ≈ 9 million operations → ~9ms on modern CPUs

Algorithm Comparison

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n³)	O(n³)	7/10	❌
Hash Map	O(n²)	O(n)	6/10	✅ (Marginally)
Two-Pointer	O(n²)	O(1)	8/10	✅ Optimal

6. Pro Mode Extras

Variants

3Sum Smaller (LC 259): Count triplets with sum < target
- Modify two-pointer condition to accumulate counts
4Sum (LC 18): Add an outer loop layer for quadlet search
3Sum with Multiplicity (LC 923): Handle counts with modulus

Interview Cheat Sheet

First Step: Always mention sorting to enable two-pointer and handle duplicates
Mention: Early termination if nums[i] > 0 (since array is sorted)
Stress Test: Ask about input constraints (negative numbers, duplicates)
Whiteboard: Draw sorted array with i, l, r markers

#15 - 3Sum