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.

Pick a sub-pattern above. Each is independently linkable — start where the problem statement points.

↑ choose one

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