3Sum

mediumTests passed 2026-11-11v1.0.0
TC: O(N^2)|SC: O(1)
Two PointersOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Sort the array first (`O(N log N)`), fix anchor `nums[i]` (skipping duplicates and breaking early if `nums[i] > 0`), and run Two Pointers on `(i+1 .. N-1)` skipping duplicates on `l` after matches.

2. Complexity Bounds & Proof

N outer anchors each run a linear O(N) two-pointer pass (ignoring output list space).

3. Minimal Idiomatic Code

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

4. Failure Modes & Interview Follow-ups

Pitfalls:- Failing to deduplicate `nums[i] == nums[i-1]` AND `nums[l] == nums[l-1]` emits duplicate triplets.
Follow-ups:- k-Sum generalizes by recursive reduction down to sorted 2-Sum.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Two Sum II - Input Array Is Sorted (O(N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.