3Sum — Sort and Two-Pointer Scan with Deduplication (LC 15)

Problem Statement#

LeetCode 15 — 3Sum (Medium)

Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0. The solution set must not contain duplicate triplets.

Constraints:

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

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

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

Why This Problem Matters#

LC 15 is one of the most frequently asked medium-difficulty problems at FAANG companies. It is a litmus test for whether a candidate genuinely understands two pointers versus having memorised the Two Sum pattern.

Two layers of difficulty catch most candidates: (1) reducing 3Sum to 2Sum — once you fix one element as the anchor, you need all pairs in the remainder that sum to its negative; (2) deduplication without a set — after sorting, you can skip duplicates in-line with pointer comparisons. Candidates who use a Set of tuples often pass correctness but fail the elegance check.

This problem is also the direct foundation for LC 16 (3Sum Closest), LC 18 (4Sum), and the general k-Sum pattern. If you understand 3Sum completely — including the deduplication logic — you can solve all of them. Interviewers at Google and Meta specifically probe: "Why do you skip nums[i] == nums[i-1]? Why not nums[i] == nums[i+1]?"

The Core Insight#

Sort the array. For each index i, the problem reduces to: find all pairs in nums[i+1 .. n-1] summing to -nums[i] — a two-pointer scan on the suffix.

Two pointers left = i + 1 and right = n - 1 scan inward:

• sum == target: record triplet, skip duplicates on both sides, advance both pointers
• sum < target: move left right to increase sum
• sum > target: move right left to decrease sum

Deduplication at three levels:

1. Anchor (i): skip if nums[i] == nums[i-1] — same anchor would produce duplicates already found
2. Left pointer: after recording a triplet, skip past all nums[left] duplicates
3. Right pointer: after recording a triplet, skip past all nums[right] duplicates

Early termination: once nums[i] > 0, no triplet can sum to zero — all remaining elements are positive.

Visual Dry Run#

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

i=1, nums[i]=-1, target=1:

i=2, nums[i]=-1: skip — nums[2] == nums[1] (duplicate anchor).

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

Solution (Optimal)#

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    n = len(nums)
 
    for i in range(n - 2):
        if nums[i] > 0:
            break
        if i > 0 and nums[i] == nums[i - 1]:
            continue
 
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[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
            elif total < 0:
                left += 1
            else:
                right -= 1
 
    return result

var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
    const n = nums.length;
 
    for (let i = 0; i < n - 2; i++) {
        if (nums[i] > 0) break;
        if (i > 0 && nums[i] === nums[i - 1]) continue;
 
        let left = i + 1, right = n - 1;
        while (left < right) {
            const total = nums[i] + nums[left] + nums[right];
            if (total === 0) {
                result.push([nums[i], nums[left], nums[right]]);
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;
                left++;
                right--;
            } else if (total < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
};

Time: O(n²) — O(n log n) sort + O(n) scan per anchor for n anchors Space: O(1) excluding output — in-place sort, no auxiliary data structure

Common Mistakes#

• Checking nums[i] == nums[i+1] instead of nums[i] == nums[i-1] for the anchor — this skips the first occurrence (which processed results) and keeps duplicates
• Forgetting to skip duplicates at left and right after recording a triplet — the same triplet gets recorded multiple times
• Not advancing both pointers after a match — causes an infinite loop
• Starting the inner two-pointer scan from index 0 instead of i+1 — allows reusing elements
• Missing the early exit when nums[i] > 0 — all remaining sums are positive, no zero-sum possible

Interview Tips#

• Always explain the deduplication direction: compare nums[i] to nums[i-1], not nums[i+1]
• The inner while loops for skipping duplicates must use left < right as a guard
• After sorting, state the reduction: "Fix nums[i], find pairs summing to -nums[i] in the suffix"
• The interviewer will ask about k-Sum generalisation — mention recursion: reduce k-Sum to (k-1)-Sum

Follow-up Questions#

• LC 16 — 3Sum Closest: same structure; track minimum absolute difference instead of exact match
• LC 18 — 4Sum: two nested anchor loops, then two pointers; O(n³) total
• General k-Sum: recurse — reduce k-Sum to (k-1)-Sum by fixing the outermost anchor; base case is 2Sum with two pointers
• Count triplets instead of listing them: when a match is found, count duplicate left values times duplicate right values and add the product

Key Takeaways#

• Sort first, then fix each element as anchor i and run two pointers on the suffix [i+1, n-1]
• Deduplication is three-level: anchor (skip nums[i] == nums[i-1]), left pointer, right pointer
• Anchor deduplication compares to the previous element — "already handled this value, skip the duplicate"
• Early exit when nums[i] > 0 — all future anchors are positive, no zero-sum triplet possible
• After recording a match, advance both pointers (after skipping duplicates) — never just advance one
• Master 3Sum and you have the toolkit for all k-Sum variants asked in FAANG interviews