In-place index hashing

40 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

You are given 3, 4, −1, 1 and asked for the smallest positive whole number that is missing. By hand: is 1 there? Yes. Is 2 there? No, so the answer is 2. Each "is it there?" is a scan of the whole list, and in the worst case you ask about 1, 2, 3, … up to n + 1, which is about n² looks.

A hash set would make each look one step, but the problem adds a twist: you are not allowed extra memory beyond a few variables. So the question becomes: where can we keep the "seen" marks without a new array?

Build the structure, one piece at a time

The key fact: the answer is always between 1 and n + 1 for a list of n numbers, because n numbers can cover at most the values 1 … n. So only the values 1 … n matter, and there are exactly n slots in the array. That is a perfect fit: let slot v − 1 be the home of value v. The array becomes its own hash table, where the index is the key.

The operation: walk the array, and whenever the value in your hand is in range 1 … n and is not already sitting at home, swap it into its home. Do not move on until the value in your hand is out of range or already home, because the swap brings a new value into the current slot. On 3, 4, −1, 1 with n = 4:

1. Index 0 holds 3; its home is index 2. Swap: −1, 4, 3, 1.
2. Index 0 now holds −1, out of range. Move on.
3. Index 1 holds 4; its home is index 3. Swap: −1, 1, 3, 4.
4. Index 1 now holds 1; its home is index 0. Swap: 1, −1, 3, 4.
5. Index 1 holds −1, out of range. Move on. Indices 2 and 3 hold 3 and 4, already home.

Second pass: read the array left to right and find the first slot whose value is not its index plus one. Slot 1 holds −1 instead of 2, so the answer is 2. If every slot is home, the answer is n + 1.

A sibling of this trick uses a sign instead of a swap: when you see value v, make the number at index v − 1 negative. A negative at index i then means "value i + 1 was seen", and the number's size is untouched so you can still read it. That version is for lists where every value is already in 1 … n.

Why it is correct

The invariant after the placing pass: for every value v in 1 … n that occurs in the array, slot v − 1 holds v. A swap only ever moves a value into its own home, and a value sitting in its home is never moved out, because we only swap when the value in hand is not home. So once v reaches slot v − 1 it stays. Every in-range value is picked up by the walk at some point and sent home, unless its home already holds another copy of v, in which case a copy is home anyway. So the invariant holds.

Then the first slot i with a wrong value means i + 1 is missing, and every smaller value is present, so i + 1 is the smallest missing positive.

Why it is fast

Count the swaps. Every swap puts at least one value into its final home, and values never leave their home, so there are at most n swaps in total, even though a single slot may trigger several in a row. Add the n steps of walking and the n steps of the second pass: at most about 3n operations, O(n) time. Extra memory is the one variable holding the value in hand, O(1). The by-hand method was O(n²); a hash set would be O(n) time but O(n) extra space.

How to recognise it in an interview

Cues: the values are promised to lie in 1 … n (or 0 … n − 1), the question is about missing or duplicated values, and the problem says "constant extra space" or "without modifying" is not required. The matching of value range to index range is the giveaway.

Say: "The values fit the indices, so I will use the array as its own hash table and park each value at index value − 1." First Missing Positive is the swap version above. Find All Numbers Disappeared in an Array is the sign version: negate slot v − 1 for each v, then report indices that stayed positive. Find the Duplicate Number is the same idea run until a value tries to go home and finds its twin already there.

02The idea in one line

Values 1..n: mark presence by negating or swapping into slot value-1.

Reach for it when: Find missing/duplicate numbers in 1..n with O(1) extra space.

Cost: O(n) time, O(1) space.

03The walk-through, step by step

The video works one example: First Missing Positive on [3,4,-1,1] via cyclic swaps. These are its captions in order, so you can follow without the video or check a step you missed.

1. The array itself is the hash: slot v−1 should hold v
2. nums[0] = 3 belongs at index 2: swap it home
3. nums[0] = -1: out of range, move on
4. nums[1] = 4 belongs at index 3: swap it home
5. nums[1] = 1 belongs at index 0: swap it home
6. nums[1] = -1: out of range, move on
7. nums[2] = 3: already home, move on
8. nums[3] = 4: already home, move on
9. Scan: index 0 holds 1 ✓
10. Scan: index 1 holds -1, not 2. Missing = 2
11. Each swap parks one value for good: O(n) time, O(1) extra space

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Arrays & Hashing: Hash the complement, Frequency counting, Canonical key hashing, Set-start expansion, Seen-set cycle detection.