3Sum Triplet Target

Hints

1. Reduce to a problem you have already solved. Fix the outer element nums[i]. What remains is: find two values in the suffix that sum to -nums[i]. That is Two Sum. Three nested loops become one loop wrapped around a linear scan.
2. Sort first, and know both reasons. Sorting enables converging pointers for the inner search, which costs O(n) per pivot with no extra memory. It also makes equal values adjacent, which is what turns duplicate suppression into a neighbour comparison instead of a set membership test.
3. Run the inner search with two pointers. With left just past the pivot and right at the end, compare the three-way sum to zero. Too small means the smallest term must grow, so advance left. Too large means the largest term must shrink, so retreat right. Each step eliminates one candidate permanently, so the scan is linear.
4. Suppress duplicate pivots by looking backwards. Before processing index i, skip it when i > 0 and nums[i] == nums[i - 1]. Looking backwards is correct because the first occurrence of a value has already explored every triplet that value can start. Looking forwards instead, with nums[i] == nums[i + 1], skips the first occurrence and loses triplets like [-1, -1, 2].
5. Suppress duplicates inside the pointer loop too. After recording a hit, advance past every copy of the value just consumed at both ends, otherwise the next iteration finds the identical triplet again.
6. Break early once the pivot is positive. In a sorted array, if nums[i] > 0 then the two larger values that follow are positive as well, so the sum cannot be zero. Break, do not continue: every later pivot is at least as large.

Solution: three approaches

Approach 1 - Triple loop: O(n^3) time, O(1) space

The baseline worth naming before discarding.

def three_sum_brute(nums):
    n, out = len(nums), 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:
                    out.add(tuple(sorted((nums[i], nums[j], nums[k]))))
    return [list(t) for t in out]

Correct, and it handles deduplication by canonicalising each hit as a sorted tuple in a set, which is the most honest way to state what "no duplicate triplets" means. The cost is C(n, 3) = n(n-1)(n-2)/6 iterations, which is Theta(n^3). At n = 3000 that is about 4.5 billion, well past the time limit. The sorted-tuple canonical form is still worth remembering, because it is the fallback deduplication strategy whenever you cannot sort the input. It is also the clearest possible statement of what the problem means by a duplicate triplet: two results collide when their multisets of values match, regardless of which indices produced them. Every faster approach is an optimisation of this test, not a redefinition of it, so when the neighbour-skipping logic in approach 2 starts to feel like folklore you can always come back here and check a disputed case against the brute force on a ten-element array. Interviewers generally want the quadratic solution, but they want to hear that you know what it is approximating.

Approach 2 - Sort plus converging pointers: O(n^2) time, O(1) auxiliary space

The expected answer. Sort once, fix a pivot, converge two pointers over the suffix.

def three_sum(nums):
    nums.sort()
    result = []

    for i in range(len(nums) - 2):
        if nums[i] > 0:                          # suffix is all positive
            break
        if i > 0 and nums[i] == nums[i - 1]:     # pivot already explored
            continue

        left, right = i + 1, len(nums) - 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

Why the pointer movement never skips an answer: the array is sorted, so for a fixed left the sum decreases monotonically as right moves down. If the current sum is too small, no choice of right below the current one can fix it, because that only makes the sum smaller. So every pair involving this left is dead and advancing left discards exactly the pairs that cannot work. The symmetric argument justifies retreating right. This is the converging-pointer invariant, proved in full in the converging pointers proof.

Why it is O(n^2) and not O(n^2 log n): the sort costs O(n log n) once. The outer loop runs n times, and each inner two-pointer scan moves left rightward and right leftward without ever reversing, so the two pointers together traverse at most n positions per pivot. That is O(n) per pivot and O(n^2) overall, which dominates the sort. The duplicate-skip while loops look like they might add a factor, but each of their iterations also advances a pointer that never goes back, so they are absorbed into the same linear budget.

Why the pivot skip looks backwards: when the loop reaches the first occurrence of a value, the two-pointer scan explores every triplet that starts with that value, including triplets that use a later copy of the same value at left. The work is complete. A second pivot with the same value would therefore reproduce exactly the same triplets. Testing against nums[i - 1] skips the later copies and keeps the first, which is what you want. Testing against nums[i + 1] skips the first copy and keeps the last, and the last copy has a shorter suffix to search, so genuine triplets such as [-1, -1, 2] disappear.

Why space is O(1) excluding output: the only storage beyond the result list is three indices and a running total. In Python, sort() is in place but Timsort's merge buffer is O(n) in the worst case, so say "O(1) auxiliary beyond the sort" rather than claiming constant flatly. The output itself can hold O(n^2) triplets in adversarial inputs and is conventionally excluded from the space bound.

Approach 3 - Hash set for the inner search: O(n^2) time, O(n) space

Worth knowing for the case where sorting is forbidden or the values are not comparable.

def three_sum_hash(nums):
    nums.sort()
    out, n = set(), len(nums)
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        seen = set()
        for j in range(i + 1, n):
            need = -nums[i] - nums[j]
            if need in seen:
                out.add((nums[i], need, nums[j]))
            seen.add(nums[j])
    return [list(t) for t in out]

Same asymptotic time, worse constants and worse memory. The inner loop rebuilds a set of size up to n for every pivot, so allocation dominates the runtime in practice even though the bound is identical. Its one advantage is that it does not need the two-pointer invariant, which makes it easier to adapt when the target is not zero or when the array cannot be reordered. The set of tuples handles deduplication at the cost of hashing every hit.

Complexity comparison

Edge cases to verify

• Fewer than three elements: the outer range(len(nums) - 2) is empty, so the function returns [] without a guard.
• All zeros: [0, 0, 0, 0] returns [[0, 0, 0]] exactly once. This is the input that catches a missing pivot skip or a missing inner skip.
• All positive or all negative: [1, 2, 3] returns [], and the nums[i] > 0 break fires immediately.
• Repeated value needed twice: [-1, -1, 2] must be reported. A forward-looking pivot skip loses it.
• No triplet despite many pairs: [0, 1, 1] returns [], exercising the loop exit rather than any early break.

Where beginners go wrong

• Skipping pivot duplicates forwards instead of backwards. The guard is i > 0 and nums[i] == nums[i - 1]. Writing nums[i] == nums[i + 1] keeps the last copy of a repeated value rather than the first, and the last copy has a shorter suffix to search, so triplets such as [-1, -1, 2] vanish. The output looks right on inputs without repeats, which is why this ships.
• Advancing the pointers before skipping duplicates. After recording a hit, the skip loops must run first and the single increment after. Swapping the order leaves each pointer parked on the last copy rather than past it, so the same triplet is recorded again on the next iteration.
• Forgetting to deduplicate inside the pointer loop at all. The pivot skip alone is not enough. With [-2, 0, 0, 2, 2] and pivot -2, the pair (0, 2) is found, and without the inner skips the next iteration finds the second 0 paired with the second 2 and reports [-2, 0, 2] twice.
• Not sorting, then using two pointers anyway. The converging-pointer invariant depends entirely on monotonicity. On an unsorted array "sum too small, move left" is not a valid deduction and the algorithm silently returns a subset of the answers.
• Using continue instead of break on a positive pivot. Both are correct, but in a sorted array every subsequent pivot is at least as large, so continue keeps scanning pivots that provably cannot work. On an all-positive array of 3000 elements that is 3000 wasted iterations instead of one.
• Mutating the caller's array without saying so. nums.sort() sorts in place. If the caller needs the original order, sort a copy and stop claiming O(1) auxiliary space. Say which you chose.

Interview follow-ups to expect

• "Make it 4Sum." Add another outer loop with its own backwards duplicate skip, giving O(n^3). The general kSum is a recursion that peels one index per level down to a two-pointer base case, costing O(n^(k-1)).
• "3Sum Closest: return the sum nearest to the target." Same sorted two-pointer skeleton, but track the minimum absolute difference instead of testing for equality. No deduplication is needed because you return a number rather than a set of triplets, which makes it strictly easier despite looking harder.
• "3Sum Smaller: count triplets with sum below the target." When the sum is under target, every position between left and right also works, so add right - left in one step and advance left. Counting in bulk is what keeps it O(n^2).
• "Why not hash the third value instead?" You can, and it is the same O(n^2) bound with O(n) space and heavier constants. Sorting wins here because it buys deduplication in the same stroke.
• "The array has 10^7 elements." O(n^2) is 10^14 operations and dead. Say so plainly, then discuss what is possible: bucketing by value when the range is small, or accepting an approximate or streaming answer. Recognising that no exact subquadratic algorithm is known for 3Sum is the right answer here.
• "Return indices instead of values." Deduplication changes meaning entirely, since distinct index triples with equal values are now distinct answers. Drop every skip and you are back to enumerating, which is why the problem is normally posed on values.

Related reading

• Two Pointers: the module this belongs to, including when converging pointers are valid and when they quietly are not.
• The Converging Pointers Proof: why discarding a whole row or column of the candidate matrix at each step is sound.
• Two Sum: the inner problem this reduces to, and the place to start if the pointer invariant is not yet obvious.