Three Sum Triplet Problem: 7 Clever Tricks That Always Work

Three Sum ends more interviews than any other array problem. It looks simple, but it'll punish sloppy thinking.

The brute force is three nested loops. That's O(n^3), dead past n = 500. The hash-set middle ground works but its dedup logic sprawls. You'll tangle yourself in tuple sets and still miss duplicates.

The winning move is sort plus two pointers. Fix one element, then run a converging pair scan on the rest. Duplicates melt away because equal values sit side by side. That's O(n^2) time, O(1) extra space, and the template for 4Sum and every k-sum follow-up. Learn it cold.

Three Numbers Summing to Zero, With No Duplicate Triplets

Given an integer array nums, return all unique triplets [a, b, c] with a + b + c == 0. Order of triplets and order within triplets don't matter, but duplicates are forbidden: [-1,0,1,2,-1,-4] yields exactly [[-1,-1,2],[-1,0,1]]. Note [-1,0,1] appears once even though -1 occurs twice.

Constraints: n up to 3,000 in some versions, values ±10^5. Output size can reach O(n^2) (all zeros), so O(n^2) time is the realistic target. The answer is value triplets, not indices — sorting is allowed.

Walk the example sorted: [-4,-1,-1,0,1,2]. i=0 (-4): need +4 from tail — none. i=1 (-1): tail [-1,0,1,2], left=-1,right=2 sum 0 → record [-1,-1,2], skip dupes. left=0,right=1 sum 0 → record [-1,0,1]. i=2 (dup -1, skip). i=3 (0): need 0 from [1,2] — none. Done: 2 triplets.

The Triple Loop: 10^9 Checks Plus a Duplicate Problem

Brute force: three nested loops over i < j < k, test the sum, dedup via a set of sorted tuples. Time O(n^3) — at n = 3,000 that's 4.5×10^9 iterations, hours in Python. Space balloons too: the tuple set can hold millions of entries before dedup. At n = 500 (20M iterations) it already exceeds limits.

The hash-set upgrade (O(n^2)): for each i, seek pairs summing to -nums[i] with a seen-set. Better time, but dedup still needs tuple sets and careful index-vs-value bookkeeping. It works yet reads poorly under pressure.

Interview play: name the cubic cost in one breath, note the set variant's dedup pain, and commit to sort + two pointers. That sequencing shows judgment, not just recall.

Sort First, Then Collapse the Inner Loop to Two Pointers

Sort nums. For each i in range(n-2): skip duplicate i; if nums[i] > 0 break (sorted tail can't reach zero). Set left = i+1, right = n-1, target = -nums[i]. While left < right: s = nums[left] + nums[right]; if s < target: left += 1; if s > target: right -= 1; else record, then skip equal neighbors on both sides and step once more.

Why it works: for fixed i, the tail is sorted, so the converging scan is exactly the sorted Two Sum — pointers move monotonically toward each other, examining each candidate pair once. Skipping adjacent equals after a hit (plus skipping duplicate i) guarantees each distinct value-triplet is emitted once: any duplicate would need the same values at the same positions, which the skips prevent. Per i the scan is O(n); n values of i give O(n^2) time, O(1) extra space beyond output. Sorting adds O(n log n), dominated by the scan.

Early exit nums[i] > 0 is free pruning interviewers love to see. Mention the output-size lower bound too: all-zeros input forces O(n^2) triplets, so O(n^2) is optimal.

The Sort-and-Two-Pointer Solution in Full Python

The code above is the complete LeetCode submission. Trace [-1,0,1,2,-1,-4] after sorting to [-4,-1,-1,0,1,2]: i=0 (-4) finds nothing; i=1 (-1) records [-1,-1,2] then [-1,0,1]; i=2 skips as dup; i=3 (0) needs 0 from [1,2], fails. Returns exactly the 2 expected triplets.

Complexity: O(n^2) time, O(1) extra space (output excluded). Sorting is in place; pointers are integers. Handles n = 3,000 within limits.

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        res: list[list[int]] = []
        n = len(nums)
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            if nums[i] > 0:
                break
            left, right = i + 1, n - 1
            target = -nums[i]
            while left < right:
                s = nums[left] + nums[right]
                if s < target:
                    left += 1
                elif s > target:
                    right -= 1
                else:
                    res.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
        return res

All Zeros, Arrays Under Three Elements, Duplicate Blocks

All zeros [0,0,0,0] must yield [[0,0,0]] exactly once — the skips collapse everything. Fewer than 3 elements returns []. No valid triplet returns []. All-positive sorted input triggers the nums[i] > 0 break instantly. Large duplicate blocks ([-2,-2,...,-2,4,4,...]) stress the skip loops; each while must be bounded by left < right.

Watch for triplet-as-indices bugs: the answer holds values, so appending [i, left, right] fails validation. Also watch integer types in static languages (sums fit in 32-bit here given ±10^5, but mention long for safety). Target-nonzero variants drop the > 0 early break — flag that when generalizing.

Why O(n^2) Cannot Be Beaten on This Problem

Time O(n^2): n outer positions times O(n) inner scans, plus O(n log n) sort absorbed into the quadratic term. Space O(1) besides output: a few integers. Optimality follows from output size — degenerate inputs force Ω(n^2) triplets, so no algorithm can run faster in the worst case.

Whiteboard closer: 'Sort once, then n sorted Two Sums; duplicates die at three skip sites.' Then bridge forward: '4Sum fixes one more index for O(n^3); k-sum is O(n^(k-1)).' That bridge converts a Medium pass into a Hard-ready signal.