Cyclic Sort
Place each number at its index by swapping; O(n) sort when values are a known bounded range like 1..n.
Arrays containing values in range 1..n: find missing, find duplicate, find smallest missing positive.
Each swap places a value at its correct index, and a value can be moved at most once, so total swaps are bounded by n. The reordering happens in place.
When an array contains n integers drawn from a known dense range (typically 0..n-1 or 1..n), each value has a 'home' index. Cyclic sort walks the array and swaps each misplaced value into its home, leaving sorted positions as a side effect. Each swap places at least one element correctly, so total swaps are bounded by n — giving O(n) time and O(1) space, beating any comparison sort.
The placement-by-swap is what makes find-missing and find-duplicate problems trivial: after the pass, scan for the first index where a[i] != i (or a[i] != i+1), and you've found the gap or extra. No hash set, no extra array.
This only works when the value-to-index mapping is well-defined and dense. If values are sparse, negative, or larger than n, the swap target is undefined and the pattern fails. The classic 'first missing positive' problem cleverly ignores out-of-range values (placing them anywhere) because they can't be the answer.
Each swap places at least one element at its final index, so even though the inner loop looks O(n^2), total swaps across the whole array are bounded by n — yielding O(n) time and O(1) space without a hash set.
- Using if instead of while in the inner loop — a single swap may bring another out-of-place value, which still needs placement.
- Off-by-one between 0..n-1 and 1..n indexing: forgetting the -1 when computing target index for 1-indexed values.
- Swapping when a[i] is already at its target (creating an infinite loop) — the loop guard must check a[i] != a[a[i] - 1], not just a[i] != i + 1, to handle duplicates correctly.
- Applying the pattern when values exceed n or are negative without first filtering them out.
- For find-all-duplicates, returning during the swap phase rather than in a separate post-pass.
- Find missing number in 0..n: cyclic sort, then scan for a[i] != i.
- Find all duplicates / all missing in 1..n: cyclic sort then post-pass.
- First missing positive: ignore values outside 1..n, then cyclic sort, then scan.
- Sign-flip variant: mark seen indices by negating a[abs(x)-1] instead of swapping — same asymptotics, different style.
int i = 0;
while (i < nums.length) {
int correct = nums[i] - 1; // or nums[i] for 0..n-1
if (nums[i] != nums[correct]) {
int tmp = nums[i];
nums[i] = nums[correct];
nums[correct] = tmp;
} else {
i++;
}
}
// now scan for the index where nums[i] != i + 1Problems using this pattern
3Easiest first · Blind 75 above NeetCode 150