Cyclic Sort
01 / The shared mechanism
When values fall in a known range [0, N] or [1, N], the index is the pointer — every element already knows where it belongs. Sort by sending each one home, or mark seen indices in place, and you solve a whole family of "missing / duplicate / disappeared" problems in linear time and constant extra space.
01 / The one-sentence essence
When values live in [0, N] or [1, N], every element knows its home index — walk the array once, and whenever arr[i] is not at home, swap it there. Each swap places one element correctly, so the loop runs in O(N).Problemfind the missing value(s)Input[3, 0, 1, 4, 2]
arr
3
0
0
1
1
2
4
3
2
4
home
0
1
2
3
4
Array of 5 values from 0..5 with exactly one missing. Send each value to its home index.
step
0 / 20
phase
sort
missing
·
0 / 20
02 / The pattern signature
# place each element at its correct index (range [0, n−1])i ← 0while i < n:home ← arr[i]if home < n and arr[home] ≠ home:swap arr[i], arr[home]else:i ← i + 1# scan once more: index where arr[i] ≠ i reveals the missing value
03 / When to recognize this pattern
"numbers in range [0, N] / [1, N]"
The defining signal. The value range matches the index range, so each value has a unique legal seat. Indices and values speak the same language.
"find the missing / duplicate / disappeared"
After sorting in place, any position where
arr[i] ≠ i is either a missing number or holds a duplicate — one final pass exposes the answer."O(N) time, O(1) extra space"
The constraint that rules out hash sets and explicit sorts. Cyclic sort gives both with nothing more than a swap counter.
"mutable input array"
The pattern rearranges
arr in place. If the input must be preserved, either copy it first or reach for the index-marking sibling pattern instead.04 / Common pitfalls
i.
Advancing
i after a swap.When you swap, the new
arr[i] might also be misplaced — re-check it before moving on. The right shape is while (arr[i] is misplaced) swap; else i++, not a simple for loop.ii.
Confusing the [0, N] vs [1, N] convention.
For values in
[1, N] the home of v is index v − 1; for [0, N] it's index v. Pick one and stay consistent — mixing them is the source of every off-by-one in this pattern.iii.
Infinite loop on duplicates.
If two equal values both belong at the same home, swapping them in circles loops forever. Guard with
arr[i] != arr[home] instead of i != home — when the target seat already holds the right value, leave it alone.05 / Go practice — on LeetCode
Four problems, ordered by difficulty. No solutions here, by design.
— / When to use which
classic cyclic sort
Use when the input is mutable and you need the elements physically at their home indices — e.g. find every missing or duplicate value.
swap-to-home · LC 268 · LC 448
index marking
Use when only the presence of each index matters and you want a one-pass mark plus a one-pass read — negate
arr[|x|−1] to record "seen".sign-flip · LC 442 · LC 41