Two Sum
Find two numbers in an array that add to a target in O(n).
How it works
Two Sum finds two indices i and j (i ≠ j) such that array[i] + array[j] === target.
The naive approach checks every pair in O(n²) time. The optimal solution uses a hash map to achieve O(n) time with a single pass:
For each element array[i], compute its complement = target − array[i]. If the complement is already in the map, a valid pair has been found — return the stored index and i. Otherwise, store array[i] → i in the map for future lookups.
Why this works: by the time we reach array[j], if array[i] = target − array[j] was seen earlier (i < j), it is guaranteed to be in the map. We never need to look back.
Key insight: instead of asking "does any earlier value pair with the current one?", we transform the search into a O(1) hash map lookup by pre-computing what we *need* at each step.
This pattern — store what you've seen, look up what you need — generalises to many array and streaming problems.
Complexity
Visualizer
Where it's used in the real world
Financial systems — transaction pair matching
Detecting debit/credit pairs that net to a specific amountReconciliation engines scan ledgers for offsetting transactions (e.g. a charge and its corresponding refund). Hashing transaction amounts allows O(1) lookup per record, reducing nightly batch reconciliation from hours to minutes on millions of rows.
Data pipelines — duplicate and collision detection
Finding elements that sum to a sentinel value indicating corruptionETL pipelines use complement-based checks to detect symmetric encoding errors or intentional watermarks. A single-pass hash-map scan scales to streaming ingestion without buffering the full dataset.
Streaming systems — real-time complement lookups
Matching bid/ask orders in exchange matching enginesOrder-book engines must continuously check whether an incoming order can be matched against a resting order at a price that sums to (or exceeds) a synthetic benchmark. Hash-map indexing gives sub-microsecond lookup at exchange-grade throughput.
Implementation
function twoSum(array: number[], target: number): [number, number] | null {
const map = new Map<number, number>(); // value → index
for (let i = 0; i < array.length; i++) {
const complement = target - array[i];
if (map.has(complement)) {
return [map.get(complement)!, i];
}
map.set(array[i], i);
}
return null; // no pair found
}
// Usage
console.log(twoSum([2, 7, 11, 15, 1, 8, 3], 9)); // [0, 1]