Two Sum

easyTests passed 2026-11-11v1.0.0

TC: O(N)|SC: O(N)

Arrays & Hashing Original Statement (leetcode).md

1. Core Invariant / The Trick

Store `{ value: index }` in a map as you iterate. Before inserting `nums[i]`, check whether `target - nums[i]` is already present.

2. Complexity Bounds & Proof

One scan performs O(1) expected hash lookup and insertion per element.

3. Minimal Idiomatic Code

def twoSum(nums: list[int], target: int) -> list[int]:
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

4. Failure Modes & Interview Follow-ups

Pitfalls:- Inserting `nums[i]` before checking `target - nums[i]` reuses the same index when `target == 2 * nums[i]`.

Follow-ups:- If input is sorted, use Two Pointers in O(1) space.

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))3Sum (O(N^2))

Browser Scratchpad

Console Output

Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.