3Sum

Problem

Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] with three distinct indices (i != j, i != k, j != k) whose values sum to exactly 0.

The answer must not contain duplicate triplets: two triplets that contain the same three values (in any order) count as the same triplet and may appear only once. The triplets themselves may be returned in any order.

Examples

• nums = [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]] -1 + -1 + 2 = 0 and -1 + 0 + 1 = 0; the second -1 in the input does not create a duplicate [-1,0,1].
• nums = [0,1,1] → [] No three values sum to zero.
• nums = [0,0,0,0] → [[0,0,0]] Four zeros yield the triplet [0,0,0] exactly once, despite many index combinations.

Constraints

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5
• With n = 3000, O(n^3) ≈ 2.7 * 10^10 is far too slow; O(n^2) ≈ 9 * 10^6 is the target.

Think about it first

TL;DR

Sort, then for each anchor run converging two pointers — O(n^2) time, O(1) extra space (beyond sort and output).

Approach 1 — Brute force: three nested loops

Try every index triple, collecting sums that hit zero; dedupe by normalizing each triplet to sorted order in a set.

def threeSum(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    found: set[tuple[int, int, int]] = set()
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    triple = tuple(sorted((nums[i], nums[j], nums[k])))
                    found.add(triple)
    return [list(t) for t in found]

• Time: O(n^3) — about 2.7 * 10^10 triple checks at n = 3000.
• Space: O(k) for the dedupe set (k = number of answer triplets).

The constraints rule it out: n^3 at n = 3000 is tens of billions of operations, several orders of magnitude beyond a typical time limit.

Approach 2 — Anchor + hash set (Two Sum inside a loop)

Fixing the first value a reduces the problem to Two Sum: find a pair summing to -a. Two Sum with a hash set is O(n), so the whole thing drops to O(n^2). Sorting first still helps, purely for clean duplicate-skipping.

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

Walkthrough on nums = [-1,0,1,2,-1,-4], sorted → [-4,-1,-1,0,1,2]:

• i = 0 (-4, target 4): seen grows {-1}, {-1,0}, ...; no complement ever found.
• i = 1 (-1, target 1): j on -1 (complement 2, not seen), on 0 (complement 1, not seen), on 1 (complement 0 — seen) → record [-1,0,1]; on 2 (complement -1 — seen) → record [-1,-1,2].
• i = 2 (-1): equals previous anchor → skipped.
• i = 3 (0, target 0): j on 1, 2 — no pair.

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

• Time: O(n^2).
• Space: O(n) for the per-anchor hash set.

This is correct and interview-acceptable, but the hash set costs memory and the duplicate handling is error-prone. The sorted two-pointer version removes both.

Approach 3 — Sort + converging two pointers (canonical)

In a sorted suffix, a pair with a given sum can be found by two pointers converging from the ends: a sum that is too small means the left value is too small (move left right); too big means move right left. Each comparison discards one element, so the pair search is O(n) with no extra memory, and sorted order makes duplicate-skipping a matter of stepping past equal neighbors.

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    n = len(nums)
    result: list[list[int]] = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # anchors are ascending; no zero-sum possible anymore
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same anchor value already fully explored
        left, right = i + 1, n - 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]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
    return result

Walkthrough on [-4,-1,-1,0,1,2]:

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

• Time: O(n^2) — O(n log n) sort + n anchors × O(n) pointer sweep.
• Space: O(1) extra (ignoring the sort’s internals and the output list).

Common pitfalls

• Deduping by comparing indices instead of values — uniqueness is defined on value triplets, so skip equal anchor values and step both pointers past equal neighbors after every hit.
• Skipping duplicates before the first use of a value (e.g. nums[left] == nums[left + 1] checks) — that forbids legitimate triplets like [-1,-1,2] and [0,0,0]; always allow the first occurrence, skip only repeats.
• Moving just one pointer after recording a match — with the other fixed, the only way to restore the sum is a duplicate pair, so both must move.
• Forgetting the nums[i] > 0 early break — not a correctness bug, but the interviewer expects the observation that a positive anchor in sorted order can never reach zero.

Pattern takeaway

Sorting converts “find a pair with sum S” from a hash-lookup problem into a converging two-pointer sweep, trading O(n) memory for O(n log n) prep — and once sorted, duplicate suppression comes free by skipping equal neighbors. The general recipe for k-Sum: fix k - 2 values with nested loops, finish with the two-pointer sweep, for O(n^(k-1)) total. When you see “all unique combinations summing to a target” on values (not indices), reach for sort + two pointers before a hash map.