Pattern Guide
Cyclic Sort & Missing Numbers
"Place each number at its correct index. Find missing/duplicate in O(n) O(1)."
Cyclic sort places each number at its correct index in-place: if nums[i] != i+1, swap nums[i] with nums[nums[i]-1]. After sorting, any index where nums[i] != i+1 reveals a missing or duplicate number. Works when numbers are in range [1..n]. Variants: multiple missing numbers, first missing positive, find duplicate without modifying array.
Problems you can solve with this pattern
4 problems · click any to start solving
// 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;
}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.
// 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;
}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).