Arrays
Cyclic Sort
Sort arrays containing numbers in a given range in O(n) with no extra space.
Cyclic Sort exploits the fact that if an array contains values in range [1..n], each value v belongs at index v-1. We can sort such an array in O(n) without comparison, by repeatedly swapping each element to its correct position.
Recognition signal: array contains numbers in range [1..n] (or [0..n-1]). Problems ask about missing/duplicate/corrupt numbers.
Algorithm:
O(n) proof: each swap places at least one element in its final position → at most n swaps total.
Common Mistakes
Infinite loop when swapping two equal values (duplicates) — check nums[i] != nums[correct] before swapping.
Range [0..n-1] vs [1..n]: adjust correct index formula accordingly.
Modifying input when "not allowed" — use XOR or math trick instead.
Not doing the cyclic sort first before scanning for missing/duplicate.