3Sum — The Deduplication Problem Every FAANG Interviewer Loves [LC 15]

Problem Statement

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. The solution set must not contain duplicate triplets.

Example 1 — basic case:

Input:  nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]

Example 2 — all zeros, deduplication is key:

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

Only one triplet even though there are four zeros. This is where most wrong answers appear.

Example 3 — no valid triplets:

Input:  nums = [1, 2, 3]
Output: []

All positive numbers — no combination can sum to zero.

• Why This Problem Matters
• Building Up From Two Sum
• Why Sorting Is The Key
• The Deduplication Logic (The Hardest Part)
• Deduplication Point 1: At the outer loop (index i)
• Deduplication Point 2: At the inner pointers l and r (after finding a valid triplet)
• Visual Dry Run
• Common Bugs
• Python Solution
• JavaScript Solution
• Complexity Analysis
• Follow-Up Questions
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

LeetCode 15 has appeared in real interviews at Google, Meta, Amazon, Microsoft, Goldman Sachs, Citadel, Bloomberg, and Atlassian. According to aggregated interview reports, it has shown up over 85 times across 36 companies — making it one of the most frequently reported medium problems in FAANG history. But the raw frequency undersells its importance.

The real reason interviewers love 3Sum is that it exposes three things simultaneously: whether you know the Two Pointer pattern, whether you can reason about sorting as a prerequisite for algorithms (not just for display), and — most critically — whether you can write correct deduplication logic under pressure. You can know the algorithm perfectly and still produce a wrong answer because you placed one deduplication check in the wrong spot. That is precisely the kind of detail interviewers probe for in follow-up questions. A candidate who breezes through Two Sum and gets asked 3Sum as a follow-up is immediately in deeper water. The extension looks small but demands a meaningfully different mental model.

Building Up From Two Sum

Two Sum asks: given an array and a target, find two indices whose values sum to target. The classic solution uses a hash map: iterate through the array, and for each element check if target - element is already in the map.

3Sum says: find all triplets summing to zero, with no duplicate triplets. The natural reduction is: for each element nums[i], solve Two Sum on the subarray to the right of i with a target of -nums[i]. This gets you to an O(n²) algorithm. But here is where the naive hash map approach breaks down:

When you use a hash map for the inner Two Sum, you get pairs, but you have no natural mechanism to avoid producing duplicate triplets. If the input has [-1, -1, 0, 2], fixing the first -1 gives a valid triplet [-1, -1, 2]. Fixing the second -1 gives the same triplet again. You could store seen triplets in a set to deduplicate, but that adds O(n) space per inner call and requires sorting each triplet before inserting into the set — messy, slow in practice, and error-prone.

Sorting the input array upfront changes everything, and it is the insight that makes the clean O(n²) solution possible.

Why Sorting Is The Key

When the array is sorted, two powerful things become true simultaneously:

1. The two-pointer inner loop works in O(n). With a sorted array and a fixed nums[i], you place l = i+1 and r = n-1. If the triplet sum is too small, move l right (increase the sum). If too large, move r left (decrease the sum). Because the array is sorted, each pointer moves monotonically, so together they sweep the subarray in O(n). Without sorting, this monotonic reasoning collapses and you need O(n) per check rather than O(1).

2. Duplicates cluster together. In a sorted array, all copies of a value are adjacent. This means you can skip duplicates with a simple while nums[i] == nums[i+1] check — no hash set needed, no sorting of individual triplets. Deduplication becomes O(1) per skip, embedded naturally into pointer movement.

These two properties are why sorting is not just an optimization — it is the structural prerequisite that makes the algorithm correct and efficient.

The Deduplication Logic (The Hardest Part)

This is where even experienced candidates write bugs. There are exactly two places where you must deduplicate, and they have different timing rules.

Deduplication Point 1: At the outer loop (index i)

if i > 0 and nums[i] == nums[i-1]:
    continue

Why i > 0? Because at i = 0 there is no nums[i-1]. If you write nums[i] == nums[i+1] instead, you skip the first occurrence of a value and process the second — which is wrong. You want to process the first occurrence and skip all subsequent ones.

The mental model: When you fix nums[i], you are choosing a "starting value" for the triplet. If that starting value is the same as the previous one, you will produce an identical set of triplets (because the subarray to the right is a subset of what the previous i already explored). Skip it.

Deduplication Point 2: At the inner pointers l and r (after finding a valid triplet)

# After recording the triplet:
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

Why do this? Once you find a valid triplet (nums[i], nums[l], nums[r]), if nums[l+1] == nums[l], adding it would produce the same triplet with a different index but identical values. You skip past all duplicates on the left, skip past all duplicates on the right, then make the final increment/decrement to move both pointers to genuinely new territory.

The timing trap: This deduplication happens after you record the triplet and before you move the pointers for the next search. Many candidates either forget this entirely, or do the skip after the move — which is off by one and causes missed results.

A critical note on the inner dedup guard: The condition must be l < r inside the while loops. If you omit it, the pointers can cross and you access an invalid index or skip the only valid triplet in a region.

Visual Dry Run

Input: [-1, 0, 1, 2, -1, -4]

After sorting: [-4, -1, -1, 0, 1, 2]

Indices: 0 1 2 3 4 5

i = 0, nums[i] = -4

• l = 1, r = 5 → sum = -4 + (-1) + 2 = -3 → too small → l++
• l = 2, r = 5 → sum = -4 + (-1) + 2 = -3 → too small → l++
• l = 3, r = 5 → sum = -4 + 0 + 2 = -2 → too small → l++
• l = 4, r = 5 → sum = -4 + 1 + 2 = -1 → too small → l++
• l = 5, r = 5 → l is not less than r → inner loop ends
• No triplets found.

i = 1, nums[i] = -1

• i = 1 > 0, nums[1] = -1, nums[0] = -4. Not equal, so no skip.
• l = 2, r = 5 → sum = -1 + (-1) + 2 = 0 → FOUND: [-1, -1, 2]
  • Skip right-side duplicates: nums[4] = 1 ≠ nums[5] = 2, no skip
  • Skip left-side duplicates: nums[2] = -1, nums[3] = 0, no skip
  • Move: l = 3, r = 4
• l = 3, r = 4 → sum = -1 + 0 + 1 = 0 → FOUND: [-1, 0, 1]
  • No adjacent duplicates to skip
  • Move: l = 4, r = 3 → l >= r → inner loop ends

i = 2, nums[i] = -1

• i = 2 > 0, nums[2] = -1, nums[1] = -1. Equal → skip (continue)

i = 3, nums[i] = 0

• l = 4, r = 5 → sum = 0 + 1 + 2 = 3 → too large → r--
• l = 4, r = 4 → l >= r → inner loop ends
• No triplets found.

Early termination: nums[4] = 1 > 0 → break the outer loop (sorted array, all remaining elements are positive, no triplet can sum to zero).

Result: [[-1, -1, 2], [-1, 0, 1]]

Common Bugs

These are the bugs that appear most often in interviews and online discussions:

Bug 1: Wrong direction of the i-deduplication check

# WRONG — skips the first occurrence, processes the second
if i > 0 and nums[i] == nums[i + 1]:
    continue

This skips processing -1 at index 1 when index 2 is also -1, causing you to miss triplets found from the first -1.

Bug 2: Deduplicating before checking i > 0

# WRONG — crashes on i = 0 with index out of bounds or wrong logic
if nums[i] == nums[i - 1]:
    continue

In Python, nums[-1] gives the last element, which is a silent bug. In other languages, it's an out-of-bounds crash.

Bug 3: Forgetting to deduplicate at l and r after a find

# WRONG — records triplet but moves only once
res.append([nums[i], nums[l], nums[r]])
l += 1
r -= 1

If nums[l+1] == nums[l], you will record a duplicate triplet on the next iteration. Example: [0, 0, 0, 0] produces [[0,0,0],[0,0,0]] instead of [[0,0,0]].

Bug 4: Not guarding the inner dedup loops with l < r

# WRONG — can push l past r
while nums[l] == nums[l + 1]:
    l += 1

If all remaining left values are duplicates, l blows past r and you access garbage data or miss the final move.

Bug 5: Using nums[i] > 0 as the only termination condition but applying it incorrectly The break on nums[i] > 0 is an optimization (if the smallest unfixed element is positive, no triplet sums to zero). But some candidates apply it before the duplicate check, causing them to exit early on the wrong iteration. The order must be: check nums[i] > 0 → break; check duplicate → continue; then run the inner loop.

Python Solution

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()                     # O(n log n) — enables two-pointer and dedup
    res = []
    n = len(nums)

    for i in range(n - 2):
        # Optimization: sorted array, no triplet sums to 0 if smallest is positive
        if nums[i] > 0:
            break

        # Skip duplicate values for the fixed element
        # Must check i > 0 to avoid comparing with a non-existent previous element
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        l, r = i + 1, n - 1

        while l < r:
            total = nums[i] + nums[l] + nums[r]

            if total == 0:
                res.append([nums[i], nums[l], nums[r]])

                # Skip duplicates on the left pointer
                # Guard with l < r to prevent crossing
                while l < r and nums[l] == nums[l + 1]:
                    l += 1

                # Skip duplicates on the right pointer
                while l < r and nums[r] == nums[r - 1]:
                    r -= 1

                # Move both pointers to genuinely new values
                l += 1
                r -= 1

            elif total < 0:
                l += 1  # Sum too small, move left pointer right
            else:
                r -= 1  # Sum too large, move right pointer left

    return res

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function threeSum(nums) {
    // Sort ascending — required for two-pointer correctness and deduplication
    nums.sort((a, b) => a - b);

    const res = [];
    const n = nums.length;

    for (let i = 0; i < n - 2; i++) {
        // Early exit: smallest unfixed element is positive, sum can only grow
        if (nums[i] > 0) break;

        // Deduplicate the fixed element — compare with PREVIOUS, not next
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        let l = i + 1;
        let r = n - 1;

        while (l < r) {
            const total = nums[i] + nums[l] + nums[r];

            if (total === 0) {
                res.push([nums[i], nums[l], nums[r]]);

                // Skip past all left duplicates (guard: l < r)
                while (l < r && nums[l] === nums[l + 1]) l++;

                // Skip past all right duplicates (guard: l < r)
                while (l < r && nums[r] === nums[r - 1]) r--;

                // Final step: move both to next distinct values
                l++;
                r--;

            } else if (total < 0) {
                l++;  // Need a larger sum
            } else {
                r--;  // Need a smaller sum
            }
        }
    }

    return res;
}

Complexity Analysis

Time Complexity: O(n²)

• Sorting takes O(n log n).
• The outer loop runs O(n) iterations.
• For each iteration, the two-pointer inner loop runs O(n) in the worst case (each pointer moves at most n steps total per outer iteration).
• Deduplication skips are absorbed into the pointer movement — they don't add an extra pass.
• Overall: O(n log n) + O(n²) = O(n²).

Is O(n²) optimal? For 3Sum, yes. A proof sketch: any algorithm that correctly outputs all k triplets must take at least O(k) time, and k can be O(n²) in the worst case (e.g., an array of zeros). So we cannot do better than O(n²) in general.

Space Complexity: O(1) extra (excluding the output array). The sort is in-place and no hash map or auxiliary data structure is used. Some interviewers count the result array and call it O(n²) — be prepared to clarify.

Follow-Up Questions

These are the natural extensions interviewers use to probe deeper understanding:

3Sum Closest (LC 16): Given nums and a target, find the triplet whose sum is closest to target and return that sum. The approach is almost identical: sort, fix i, two pointers, but instead of checking for zero you track the minimum absolute difference seen so far. O(n²) time.

4Sum (LC 18): Find all unique quadruplets summing to target. Add one more outer loop fixing a second element j = i+1..n-1, then run the same two-pointer inner loop. O(n³) time. This generalizes to kSum: recursively reduce k-Sum to (k-1)-Sum until you reach 2Sum as the base case.

3Sum Smaller (LC 259): Given nums and a target, count triplets whose sum is strictly less than target. Sort, fix i, two pointers. When nums[i] + nums[l] + nums[r] < target, all pairs with a left pointer between l and r-1 also satisfy the condition (since the array is sorted), so add r - l to the count and move l right. O(n²) time with a clever counting trick.

3Sum With Multiplicity (LC 923): Count the number of ordered triplets with value sum equal to target, with repetition of elements allowed. This changes the counting logic inside the two-pointer loop to account for choosing multiple copies of the same value. O(n + target) with a frequency map or O(n²) with two pointers.

This Pattern Solves

The "sort + fix one element + two pointers" pattern is a generalization you will encounter repeatedly:

• Container With Most Water (LC 11): Two pointers on a sorted-by-position structure
• Trapping Rain Water (LC 42): Two pointers tracking left/right max
• 4Sum (LC 18): Two fixed elements + two pointers
• Valid Triangle Number (LC 611): Fix largest side, two pointers for the other two
• Two Sum II (LC 167): The direct 2-pointer base case
• Boats to Save People (LC 881): Sort + greedy two pointer

Every time you see "find k elements summing to target with no duplicates in a non-sorted array," your first instinct should be: sort first, then reduce to a two-pointer base case.

Key Takeaway

3Sum is medium on paper but behaves like a hard problem in interviews because the deduplication logic has two separate locations, different timing rules, and subtle off-by-one conditions at each. The fundamental insight is that sorting is not incidental — it is load-bearing: it enables the O(n) two-pointer sweep and makes deduplication an O(1) per-skip operation instead of requiring a hash set. Get the deduplication right — specifically nums[i] == nums[i-1] (not nums[i+1]) at the outer loop, and the guarded skip loops after a find at the inner level — and the rest of the algorithm is straightforward two-pointer mechanics you can derive from first principles.