Pattern Reference
Cyclic Sort
"Place each number at its correct index in O(n). For problems with numbers 1..n."
Loading...
Deep Dive Tutorial
Cyclic sort: iterate array; while nums[i] is not at its correct index (nums[i]-1 != i), swap it to its correct position. After one pass, scan for mismatches. O(n) time, O(1) space. Key insight: each element is swapped at most once, so total swaps ≤ n. Works for numbers in [1..n] range. For duplicates: nums[i] == nums[nums[i]-1] means nums[i] is the duplicate.
Cyclic sort and find all missing numbers
// Place each number at index num-1
function cyclicSort(nums) {
let i = 0;
while (i < nums.length) {
const correct = nums[i] - 1; // where nums[i] should go
if (nums[i] !== nums[correct]) {
[nums[i], nums[correct]] = [nums[correct], nums[i]]; // swap to correct position
} else {
i++; // already at correct position (or duplicate, skip)
}
}
return nums;
}
// Find all missing numbers in [1..n]
function findAllMissing(nums) {
cyclicSort(nums);
const missing = [];
for (let i = 0; i < nums.length; i++)
if (nums[i] !== i + 1) missing.push(i + 1);
return missing;
}Worked Problems
refresh-cw
Cyclic sort pattern: When numbers are in range [1..n], each number has a natural "home" index (value-1). Place everything at its home, then scan for mismatches.
Marking trick (no modification): Negate nums[|num|-1] to mark index as visited. Works for finding missing/duplicate in O(n) O(1) without cyclic sort.
When cyclic sort doesn't apply: Numbers not in [1..n] — use HashSet O(n) space, or Floyd's cycle detection if problem models a linked list (each value points to next index).
Marking trick (no modification): Negate nums[|num|-1] to mark index as visited. Works for finding missing/duplicate in O(n) O(1) without cyclic sort.
When cyclic sort doesn't apply: Numbers not in [1..n] — use HashSet O(n) space, or Floyd's cycle detection if problem models a linked list (each value points to next index).