Hashing
Map a value to its index
Why it matters
Matching two records to a required total appears in payment reconciliation, inventory bundles, and interview problems. Trying every pair repeats almost the same search as the list grows. For nums = [3, 2, 4] and target = 6, the solution must return two distinct indexes without quadratic pair checks.
Example
Two Sum
Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target.
- Input
- nums = [3, 2, 4], target = 6
- Output
- [1, 2]
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Two Sum
nums = [3, 2, 4], target = 6→[1, 2]
The baseline, Check every pair, is O(n²) · O(1). The better model below keeps this exact input and removes that bottleneck.
In [3, 2, 4], when x = 4 at index 2, the needed value is 2, already at index 1. Rather than check all three index pairs, map earlier values to their indexes and retrieve 2 directly.
At index 0 of nums = [3, 2, 4], x is 3 and need is also 3. seen is empty, so store 3 → 0 only after the lookup. That order prevents index 0 from pairing with itself.
At index 1, x = 2 needs 4, which is not stored, so add 2 → 1. At index 2, x = 4 needs 2. The map returns index 1 immediately, giving [1, 2]. Each entry records both the earlier value and where it appeared.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.