Two Pointers · LC #15

3Sum

Sort + fix one element + two-pointer search for the pair that completes the triplet. Duplicate-skipping logic is the subtle piece that trips most candidates.

mediumLC #15AMZ★★★GOO★★META★★★MSFT★★AAPL★★NVDA★TSLA★

Mark as done

Confidence

Ask GPT Practice on LeetCodePractice

Statement

Problem & Approach

Problem statement, sample I/O, and key reasoning.

Given integer array `nums`, return all unique triplets `[nums[i], nums[j], nums[k]]` where `i ≠ j ≠ k` and `nums[i] + nums[j] + nums[k] == 0`. No duplicate triplets in the output.

Sample I/O

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

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

Intuition

How to Think About It

Intuition

Brute force is O(n³). Sorting first unlocks two key optimisations: (1) two-pointer reduces the inner pair search to O(n), giving O(n²) total; (2) adjacent duplicates can be skipped in-place, guaranteeing uniqueness without a set.

Core Concept

Sort nums. For each index i (skip if nums[i] == nums[i-1] when i > 0): run two-pointer with l=i+1, r=n-1 looking for sum == -nums[i]. If sum < 0 → l++; if sum > 0 → r--; if sum == 0 → record triplet, skip duplicate l values, skip duplicate r values, then l++/r--.

When to use

Any k-sum problem (reduce to (k-1)-sum via sorting + fixing); detecting triplets/quadruplets with a target sum.

When NOT to use

When you cannot sort (need original indices). When k is large - use DP or meet-in-the-middle instead.

Key Insights

What to Know Cold

Sorting is the prerequisite - it enables two-pointer AND duplicate skipping.
Skip duplicate i values at the outer loop start with `if i > 0 and nums[i] == nums[i-1]: continue`.
After recording a valid triplet, advance PAST duplicate l and r values before moving pointers.
Early termination: if nums[i] > 0 after sorting, no triplet can sum to 0 (all elements to the right are ≥ nums[i]).
3Sum reduces to Two Sum: fix one element, run Two Sum on the rest - a common generalisation pattern.

1 example

Worked Examples

Sort + Fix + Two Pointer with Duplicate Skipping

[-1,0,1,2,-1,-4] → sorted [-4,-1,-1,0,1,2]. Find all unique zero-sum triplets.

Fix i=1 (nums[i]=-1). l=2, r=5. Sum=-1+-1+2=0 → record [-1,-1,2], skip dup l, skip dup r. l=3,r=4: -1+0+1=0 → record [-1,0,1]. Continue. i=2 skipped (dup of i=1).

def threeSum(nums: list[int]) -> list[list[int]]:
    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:
                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
            elif s < 0: l += 1
            else: r -= 1
    return res

Highest-frequency medium at AMZ and META. Tests sorting prerequisite, two-pointer, AND duplicate-skip logic simultaneously - a canonical problem for FAANG prep.