Place each number at its correct index in O(n) time using in-place swaps, then scan for anomalies.
Cyclic sort is a technique for arrays containing numbers in a known range (typically 0 to n or 1 to n). The idea is simple: every number has a "home" index. We iterate through the array and, at each position, keep swapping the current number to its correct index until the current position holds the right value (or an unavoidable duplicate).
For an array of numbers in range [0, n], number v belongs at index v. We scan left to right. At each index i, if nums[i] != i, we swap nums[i] to its correct position. After the sort, any index where nums[i] != i reveals a missing or duplicate number.
Why does this work? Because each number has exactly one "correct" index, swapping always makes progress: every swap places at least one number in its home position. After at most n swaps, every number that can be placed correctly is placed correctly. The positions that still have the "wrong" number reveal the missing or duplicate values.
Look for these recognition signals in the problem statement. If you spot one, cyclic sort is very likely the intended O(n) time, O(1) space approach.
"Numbers in range [1, n]" or "[0, n]"
"Find the missing number"
"Find the duplicate"
"O(1) extra space" with contiguous range
The key clue: You have an array of n elements where the values come from a contiguous range of size n (or n+1). The array is essentially a permutation with anomalies. Cyclic sort exploits the fact that each value maps directly to an index, turning the array into its own hash table.
Given an array of n distinct numbers in range [0, n], one number is missing. Place each number at its "home" index (value v goes to index v). After sorting, the index whose value does not match is the missing number.
Find the missing number from range [0, 3]. Expected result: 2
Given an array of n numbers where values are in range [1, n] and some appear twice, we use cyclic sort with a twist: during swapping, if the target index already holds the correct value, we have found a duplicate. This detects all duplicates in O(n) time, O(1) space.
Range [1, 8], n = 8. Value v belongs at index v-1. Find all duplicates. Result: [2, 3]
The collision trick: When you try to swap nums[i] to its target index and the target already holds the correct value (nums[i] == nums[target]), you have found a duplicate. You skip the swap and move on. After the full pass, any index i where nums[i] != i+1 means the expected value i+1 is missing and nums[i] is a duplicate.
Here are the annotated templates for the two main cyclic sort variants. The key difference is the index mapping: [0, n] range maps value v to index v, while [1, n] range maps value v to index v - 1.
// Find the missing number in [0, n] int missingNumber(int[] nums) { int n = nums.length; int i = 0; while (i < n) { int correct = nums[i]; // value v belongs at index v if (nums[i] < n && nums[i] != nums[correct]) { // Swap nums[i] to its correct index int tmp = nums[i]; nums[i] = nums[correct]; nums[correct] = tmp; } else { i++; // already correct or out of range } } // Scan: the index where nums[i] != i is the answer for (i = 0; i < n; i++) { if (nums[i] != i) return i; } return n; // all [0, n-1] present, so n is missing }
// Find all duplicates in [1, n] List<Integer> findDuplicates(int[] nums) { int i = 0; while (i < nums.length) { int correct = nums[i] - 1; // value v belongs at index v-1 if (nums[i] != nums[correct]) { int tmp = nums[i]; nums[i] = nums[correct]; nums[correct] = tmp; } else { i++; } } List<Integer> result = new ArrayList<>(); for (i = 0; i < nums.length; i++) { if (nums[i] != i + 1) { result.add(nums[i]); // nums[i] is a duplicate } } return result; }
while, not for. Notice we use while (i < n) and only increment i when the current position is resolved. This is because a single index may need multiple swaps before it holds the correct value. A for loop that always increments would miss these cases.
Let us trace through a complete cyclic sort step by step, showing every swap and the array state at each stage.
Value v belongs at index v. Missing number: 4
| STEP | ACTION | ARRAY |
|---|---|---|
| i=0 (val 2) | 2 != 0, swap [0]↔[2] | [1, 3, 2, 0, 5] |
| i=0 (val 1) | 1 != 0, swap [0]↔[1] | [3, 1, 2, 0, 5] |
| i=0 (val 3) | 3 != 0, swap [0]↔[3] | [0, 1, 2, 3, 5] |
| i=0 (val 0) | 0 == 0, correct. i++ | [0, 1, 2, 3, 5] |
| i=1 (val 1) | 1 == 1, correct. i++ | [0, 1, 2, 3, 5] |
| i=2 (val 2) | 2 == 2, correct. i++ | [0, 1, 2, 3, 5] |
| i=3 (val 3) | 3 == 3, correct. i++ | [0, 1, 2, 3, 5] |
| i=4 (val 5) | 5 ≥ n (n=5), skip. i++ | [0, 1, 2, 3, 5] |
Notice the pattern: Multiple swaps can happen at the same index (i=0 required 3 swaps), but the pointer i only advances once the current position is resolved. Despite this, the total number of swaps across the entire algorithm is at most n, because each swap places exactly one element in its final position and that element is never moved again.
These are the classic LeetCode problems that use the cyclic sort pattern, listed in rough order of difficulty.
Practice tip: Start with #268 (straightforward missing number). Then try #448 (find all missing numbers, same approach but collect multiple results). #442 is the mirror: find duplicates instead of missing. #41 (First Missing Positive) is the hardest because the range is not given explicitly—you must realize the answer must be in [1, n+1] and adapt the cyclic sort accordingly.
Enter an array and step through the cyclic sort algorithm. Watch each swap place a number at its correct index, then see the scan reveal missing and duplicate numbers.
The while loop might seem like it could run O(n) swaps at a single index, making the total O(n²). But each swap places exactly one element into its final, correct position. Once an element reaches its home index, it is never moved again. Since there are at most n elements, there are at most n total swaps across the entire algorithm. Combined with the linear scan at the end, the total time is O(n + n) = O(n).
Space: The sorting is done entirely in-place by swapping elements within the input array. No extra data structures are needed. Total extra space: O(1). This is the key advantage over a hash set approach, which requires O(n) space.
Amortized analysis: The same reasoning applies as with other "while inside while" patterns. The inner while loop's total iterations across all outer iterations is bounded by n. Think of it this way: there are n "swap tokens" total. Each swap uses one token and permanently resolves one element. Once all tokens are spent, the algorithm terminates.
Every value has a home index. The fundamental insight of cyclic sort: value v belongs at index v (for range [0, n]) or index v-1 (for range [1, n]). This bijection turns the array into its own hash map, requiring zero extra space.
Use while, not for, and swap in place. At each index, keep swapping until the current position holds the correct value (or a value you cannot place). Only then advance the pointer. A for loop that always increments would skip unresolved positions.
Anomalies reveal the answer. After the cyclic sort pass, any index where nums[i] != i (or nums[i] != i+1) indicates either a missing number (the expected value is absent) or a duplicate (the current value is a repeat occupying the wrong slot).
Handle out-of-range values carefully. Values that fall outside the valid range (e.g., n in a range [0, n] array of size n) cannot be placed. Skip them during the sort phase. They will naturally occupy the position of the missing number.
At most n swaps total = O(n). Each swap permanently places one element. No element is moved more than once after reaching its home. Despite the nested while loop, the total number of swaps is bounded by n, making the algorithm linear. Combined with O(1) space, this is optimal for this class of problems.