3Sum — InterviewPrepKit

Solving tips

Sort first, then fix an anchor i and run converging two pointers on the suffix; this hits the O(n^2) target versus O(n^3) brute force.
Dedupe on values, not indices: skip an anchor equal to its predecessor, and after recording a hit step both pointers past equal neighbors.
When the triplet sum is too small move left up, too big move right down, equal record and move both inward.
Break early once nums[i] > 0 (no zero-sum possible in ascending order); O(1) extra space beyond sort and output.

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

Hint 1

Fix the first element `a`. The rest of the problem becomes: find two other elements summing to `-a` — a Two Sum subproblem inside a loop.

Hint 2

Sorting the array costs only `O(n log n)` and buys you two things at once: a way to find pairs by moving pointers, and a way to skip duplicates by skipping equal neighbors.

Hint 3

After sorting, for each anchor index `i`: run `left = i + 1`, `right = n - 1`; if the three sum below zero move `left` up, above zero move `right` down, equal — record and step both past all equal neighbors. Also skip anchors equal to their previous value, and stop early once `nums[i] > 0`.

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.

class Solution:
    def threeSum(self, 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 kill it outright: n^3 at n = 3000 is tens of billions of operations, several orders of magnitude past what a time limit allows.

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

The insight: 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.

class Solution:
    def threeSum(self, 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.

Correct and interview-acceptable, but the hash set costs memory and the duplicate handling is fiddly — the sorted two-pointer version removes both.

Approach 3 — Sort + converging two pointers (canonical)

The insight: in a sorted suffix, a pair with a given sum can be found by two pointers converging from the ends — sum too small means the left value is too small (move left right); too big means move right left. Each comparison permanently 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.

class Solution:
    def threeSum(self, 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]:

i (anchor)	left/right values	total	action
0 (`-4`)	`-1` / `2`	-3	left += 1
0 (`-4`)	`-1` / `2`	-3	left += 1
0 (`-4`)	`0` / `2`	-2	left += 1
0 (`-4`)	`1` / `2`	-1	left += 1 → pointers meet
1 (`-1`)	`-1` / `2`	0	record `[-1,-1,2]`, move both
1 (`-1`)	`0` / `1`	0	record `[-1,0,1]`, move both → cross
2 (`-1`)	skipped (== previous anchor)
3 (`0`)	`1` / `2`	3	right -= 1 → pointers meet

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.