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 [1, N] and you only need to know which indices were seen, the array itself becomes the bit set — negate arr[|v|−1] to mark "index v−1 seen". A final scan turns positive entries into the answer.
Problemfind missing valuesInput[4, 3, 2, 7, 8, 2, 3, 1]
arr
4
0
3
1
2
2
7
3
8
4
2
5
3
6
1
7
1..n
1
2
3
4
5
6
7
8
Array of 8 values in [1, 8]. Mark phase next: for each value, flip the sign of its home cell.
step
0 / 26
phase
mark
missing
·
0 / 26

02 / The pattern signature

# mark phase — sign-flip the home cell of each valuefor i in 0..n−1:v ← abs(arr[i])if arr[v − 1] > 0:arr[v − 1] ← −arr[v − 1]# read phase — positive entries reveal missing indicesfor i in 0..n−1:if arr[i] > 0: i + 1 was never seen

03 / When to recognize this pattern

"values are positive and bounded by n"
The precondition that makes sign-flipping a safe channel for an extra bit. The sign carries the "seen" flag; the magnitude still carries the original value. One slot, two facts.
"missing / duplicate / disappeared, O(1) extra space"
Without the space constraint a hash set is simpler. With it, indices become the only legal storage — and sign-flipping is the cleanest way to use them.
"presence only, position not required"
You don't need elements physically at home — you only need to recover which indices appeared. That's strictly less work than full cyclic sort.
"absolute value when reading"
After the first mark, entries can be negative. Always read the magnitude: v = |arr[i]| — using the raw value would compute the wrong home index on the second visit.

04 / Common pitfalls

i.
Negating twice on a duplicate.
If v appears twice, naive negation flips its home back to positive on the second visit — the "seen" mark is lost. Guard with if arr[v−1] > 0 before flipping, or read the sign to detect duplicates first.
ii.
Forgetting the abs on the read.
After the first few marks the value at arr[i] may already be negative. Use v = |arr[i]| when computing the home index — otherwise you'll index into negative territory and crash, or silently mark the wrong cell.
iii.
Zero and out-of-range values.
The trick assumes values in [1, n]. Zeros have no sign to flip, and out-of-range values point nowhere — pre-process them (e.g. clamp to n + 1) or the marking phase silently corrupts the array.

05 / Go practice — on LeetCode

Four problems, ordered by difficulty. No solutions here, by design.

01Find All Numbers Disappeared in an Array— LC 448easy→02Find All Duplicates in an Array— LC 442medium→03Find the Duplicate Number— LC 287medium→04First Missing Positive— LC 41hard→

— / 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