LeetCode 15 · Two Pointers · concept: two-pointers

Problem

Return all unique triplets [a, b, c] in nums with a + b + c == 0. No duplicate triplets in the output.

nums = [-1, 0, 1, 2, -1, -4]  ->  [[-1, -1, 2], [-1, 0, 1]]

Approach 1 — brute force (all triples)

Three nested loops, dedupe with a set. O(n³) time — too slow, and the dedup is awkward.

Approach 2 — sort, then fix-one + two-pointer (optimal)

Reduce 3Sum to n runs of Two Sum II. Sort the array; then for each index i, look for two elements in the rest of the array summing to -nums[i], using the converging two-pointer sweep. Sorting is what enables both the two-pointer step and clean duplicate-skipping.

def threeSum(nums):
    nums.sort()
    res = []
    for i in range(len(nums)):
        if nums[i] > 0:                    # sorted: no way three ≥0 sum to 0
            break
        if i > 0 and nums[i] == nums[i - 1]:
            continue                       # skip duplicate anchor
        l, r = i + 1, len(nums) - 1
        while l < r:
            total = nums[i] + nums[l] + nums[r]
            if total < 0:
                l += 1
            elif total > 0:
                r -= 1
            else:
                res.append([nums[i], nums[l], nums[r]])
                l += 1
                r -= 1
                while l < r and nums[l] == nums[l - 1]:   # skip duplicate seconds
                    l += 1
    return res

Time O(n²), space O(1) (ignoring output and sort). The outer loop is O(n), each two-pointer sweep is O(n).

The duplicate handling — the hard part

There are two independent dedup points, both relying on the sort:

  1. Anchor — if i > 0 and nums[i] == nums[i-1]: continue skips a repeated first element, so you don’t emit the same triplet family twice.
  2. Second element — after recording a hit, while nums[l] == nums[l-1]: l += 1 skips repeated middle values.

Sorting groups equal values adjacently, which is the only reason “skip if same as previous” works. Getting duplicates right — not the two-pointer sweep — is what makes 3Sum a step up from Two Sum II.

Complexity summary

ApproachTimeSpace
Brute forceO(n³)O(n)
Sort + two-pointerO(n²)O(1)*

* excluding output.

Key insight

k-Sum reduces to (k−1)-Sum by fixing one element and recursing. 3Sum = “for each anchor, solve Two Sum II on the remainder.” The nums[i] > 0 early break and the two-tier duplicate skip are the details that separate a correct, efficient solution from a slow or buggy one. 4Sum is the same idea one level deeper (two nested anchors + two pointers).

↑ Back to NeetCode 150 — Solved