Lesson 9 · Core patterns

Cyclic sort & index-as-hash

📖 Walk me through it — plain English

Here is the setup. You are handed an array (a numbered list of slots, counting from index 0) that contains n numbers, and those numbers are promised to come from a tidy range — exactly 1 to n, or 0 to n-1. The clever observation is that each value already announces where it should live. If the range is 1..n, then the value v belongs at index v-1 (so 1 goes to slot 0, 2 to slot 1, and so on). That means the array can act as its own lookup table — "the index is the hash" — so we never need a separate hash set. A hash set is just an auxiliary box that remembers which numbers you have seen; here the position in the array remembers it for us, for free.

Cyclic sort is the technique that puts every number home. We keep one pointer i. We look at nums[i], figure out its correct home index j = nums[i] - 1, and — if it is not already there — we swap it into that home slot. Crucially, after a swap we do not move i forward, because a brand-new value just landed under our pointer and it also needs sorting. We only step i forward once the value in front of us is already home (or is junk we cannot place).

Think of a classroom with assigned, numbered seats. You stand at the front, pick up the person sitting in seat 1, and walk them to their assigned seat. Whoever was sitting there gets handed to you, so you walk that person to their seat, and so on — a little chain of swaps. You only return to the front and move to the next seat once seat 1 is occupied by the right person. Every time you seat someone correctly, that person is done forever, which is why the whole thing is fast.

Let us trace a tiny example with a missing-and-duplicate twist: [3, 4, 1, 3], so n = 4 and the home of value v is index v-1. The accent (bright) cell marks the slot pointer i is examining right now.

Start. i = 0. We look at slot 0, which holds 3. The home for 3 is index 3-1 = 2.

Slot 2 currently holds 1, which is different from 3, so we swap. Now 3 is home. We do NOT advance i — re-examine slot 0.

Still i = 0. Slot 0 now holds 1, whose home is index 1-1 = 0 — it is already home. Nothing to do, so advance i to 1.

i = 1. Slot 1 holds 4, home index 4-1 = 3. Slot 3 holds 3, which differs from 4, so swap. 4 lands home; stay at i = 1.

Still i = 1. Slot 1 now holds 3, home index 2. But slot 2 ALREADY holds a 3 — destination equals our value (a duplicate!). The guard nums[i] != nums[j] fails, so we DON'T swap (this is what prevents an infinite loop). Advance i to 2.

i = 2 holds 3 (home index 2, already there) and i = 3 holds 4 (home index 3, already there). Both are settled, so i walks off the end. Pass complete; the array is as sorted as it can get.

Final scan: walk left to right, checking that slot i holds i+1. Slot 0 = 1 (correct). Slot 1 should hold 2 but holds 3 — first mismatch! The expected value 2 is the MISSING number, and the 3 squatting there is the DUPLICATE.

Why is this O(n) time even though there is a loop that sometimes refuses to advance? Look at what each swap accomplishes: it drops at least one number into its permanent home, and a number that is home is never touched again. There are only n homes, so at most n swaps can ever happen across the whole run. On top of that, i advances at most n times (the no-op steps). Add those up and the total work is proportional to n — linear time. And because every move is a swap inside the same array, we use only O(1) extra space (a constant amount, no growing helper structure).

The one rule you must never break: decide whether to swap by comparing against the destination slot (nums[nums[i]-1]), not against where the value currently sits. If you instead test "is nums[i] equal to i+1?", then two copies of the same number can never both be satisfied, and the pointer spins forever. Checking the destination is exactly what let us notice the duplicate 3 above and calmly move on.

When an array holds n numbers drawn from a known range — exactly 1..n or 0..n-1 — each value already tells you where it belongs. The value v wants to sit at index v-1 (for 1-indexed ranges), so the array itself doubles as a hash table: the index is the hash. Cyclic sort walks one pointer i, and as long as nums[i] is not already home, it swaps it into its correct slot instead of advancing. Picture sorting numbered seats: you pick up the person in front of you, walk them to their seat, grab whoever was sitting there, and repeat — you only move on once the person in front of you belongs there. Because every swap drops at least one number into its final position, you do at most n productive swaps total, giving O(n) time, O(1) space. The payoff: after the pass, scan once — the first index whose value is wrong exposes the missing or duplicate number for free, no extra structure needed.

Trigger signals

Array of n numbers in range 1..n or 0..n-1
"Find the missing / duplicate number"
"Smallest missing positive"
Must be in-place, O(1) extra space
You're tempted to reach for a hash set or sort

Canonical problems

Missing Number (range 0..n)
Find All Numbers Disappeared in an Array
Find the Duplicate Number
First Missing Positive (range filtered to 1..n)
Set Mismatch (the dup + the missing)

Template — Cyclic placement + missing/duplicate scan

def cyclic_sort(nums):
    n = len(nums)
    i = 0
    while i < n:
        # value v belongs at index v-1 (1-indexed range 1..n)
        j = nums[i] - 1
        # swap only if in range AND target slot isn't already correct
        if 0 <= j < n and nums[i] != nums[j]:
            nums[i], nums[j] = nums[j], nums[i]   # don't advance i
        else:
            i += 1
    # first index whose value != i+1 is the answer
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1   # missing; nums[i] is the duplicate sitting here
    return n + 1   # all of 1..n present (First Missing Positive case)

function cyclicSort(nums: number[]): number {
  const n = nums.length;
  let i = 0;
  while (i < n) {
    const j = nums[i] - 1;            // correct index for value nums[i]
    if (j >= 0 && j < n && nums[i] !== nums[j]) {
      [nums[i], nums[j]] = [nums[j], nums[i]]; // place it, re-check i
    } else {
      i++;
    }
  }
  for (let k = 0; k < n; k++) {
    if (nums[k] !== k + 1) return k + 1; // missing value
  }
  return n + 1;
}

Key trick — the loop guard is everything

Condition nums[i] != nums[j] (where j = nums[i]-1) is the safety belt: it says "swap only if the destination doesn't already hold this value." On a duplicate, the target slot is already filled with the same number, so the guard fails and you advance — no infinite swap.
Never use nums[i] != i+1 as the swap guard. Two equal values can never both be placed, so the pointer would spin forever. Always compare against the destination slot nums[nums[i]-1].
Swaps that fire do not advance i — you re-examine the new value now sitting at i. You only step forward when i is settled.

Complexity & gotchas

O(n) time, O(1) space. The while looks nested but each successful swap lands one value permanently; total swaps <= n, plus <= n no-op advances.
1-indexed vs 0-indexed. Range 1..n → correct index is v-1. Range 0..n-1 → correct index is v (drop the -1) and the final-scan target becomes i, not i+1.
First Missing Positive mixes in junk (negatives, zeros, values > n). The bounds check 0 <= j < n simply ignores out-of-range values — they get parked and skipped, and the first wrong slot is your answer; if none, return n+1.
Missing Number, range 0..n has n+1 possible values but only n slots, so one number can't fit by index — handle by summing (Gauss) or XOR, or extend the array conceptually; pure cyclic sort fits cleanest on the exact 1..n / 0..n-1 shape.
Duplicate read-out. After sorting, at the first bad index i: the expected value i+1 is missing, and the value actually sitting there is the duplicate — Set Mismatch returns both.
You are mutating the input. If the caller needs it intact, copy first (costs the O(1)-space guarantee) or confirm in-place is allowed.

Find the missing number with the sum trick — run it live:

→ Going deeper: Index-as-hash and binary search both exploit sorted structure. See Binary search.