Cyclic Sort
The Intuition
Cyclic sort is a niche technique with a strict precondition: the array must contain numbers from a contiguous small range, typically 0..n or 1..n. When that holds, a regular sort wastes work. There is a way to sort in O(n) time using O(1) extra space, and it falls out of one observation: every value has a known correct position.
For range 1..n, the value v belongs at index v - 1. For range 0..n, value v belongs at index v. Walk the array. If nums[i] is already at its correct index, advance. Otherwise swap it to where it belongs. The displaced element from that target position is now at index i, and may also need to be moved. Don't advance i yet. Keep swapping until nums[i] is either correctly placed at i, out of range, or a duplicate of the value already at the target.
Why is this O(n) and not O(n²)? Each successful swap places at least one element at its final position permanently. After n successful swaps, the array is fully sorted. The swap cost is bounded by the total work, not the number of outer iterations.
The reason cyclic sort is interview-worthy is what comes after the sort. With every legal value parked at its index, a single linear scan finds whatever the question asks. No hash map needed. Constant extra space.
Three LeetCode problems fall out of this technique, all shown in the code below.
Find Missing Number (LC 268). The input is an array of size n containing distinct values from 0..n with exactly one number missing. After cyclic sort, the answer is the first index where nums[i] != i. If every index matches, the missing number is n itself.
First Missing Positive (LC 41). The input is an arbitrary array of integers (negatives, zero, large values, duplicates). The answer is the smallest positive integer not present. After placing each value v in 1..n at index v - 1 and ignoring out-of-range values, the answer is the first index where nums[i] != i + 1. If every index matches, the answer is n + 1.
Find All Duplicates (LC 442). The input is an array of size n with values in 1..n where some values appear once and others appear twice. After cyclic sort, the values that ended up at the wrong index are the duplicates. Walk the array once at the end, collect every nums[i] where nums[i] != i + 1.
The swap guard matters. Use nums[i] != nums[nums[i] - 1] rather than nums[i] - 1 != i. The first version stops swapping when a duplicate is detected (both positions hold the same value), which is exactly what you want for "find duplicates" type problems. The second version risks infinite loops on duplicates.
- Input is guaranteed to be in a known range like
0..n,1..n, or1..n+1 - Need to find missing, duplicate, or first-missing-positive in O(1) space
- Allowed to mutate the input array
- Range size matches the array size (or differs by exactly 1)
- Values are unbounded or in an unknown range (use a hash set instead)
- Cannot mutate the array (use marking with negation, or a hash set)
- Values can be repeated arbitrary times and the question is about frequency (use a hash map)
Variations:
- Marking with negation: Walk once, for each
nums[i]flip the sign ofnums[abs(nums[i]) - 1]to mark "seen". Indexes that stay positive correspond to missing numbers. Same O(n) time, O(1) space, but harder to reason about than cyclic sort. - XOR trick: For Missing Number specifically, XOR all values with all indexes. Pairs cancel, leaving the missing number. Beautiful but problem-specific.
- Floyd's tortoise and hare on indexes: For Find the Duplicate Number (LC 287), treat the array as a linked list where index
ipoints tonums[i]. The duplicate is the entrance of the cycle.
- Empty array (return whatever the spec says, often 0 or 1)
- Single element
- All values out of the valid range (no swaps happen, scan returns the first missing)
- Multiple duplicates of the same value
- Array already sorted (no swaps happen, just one pointer pass)
Key Points
- •Works when input contains numbers in a known small range like 1..n or 0..n
- •Each number has a target index (value minus 1 for 1..n, or value for 0..n)
- •Swap until index holds the correct value, then advance
- •After sorting, scan once to find missing, duplicate, or out-of-range
- •Beats hashing in O(1) extra space when the range constraint holds
Code Template
1 # Find Missing Number (LC 268). Range is 0..n with one number missing.
2 def missing_number(nums):
3 n = len(nums)
4 i = 0
5 while i < n:
6 if nums[i] < n and nums[i] != i:
7 j = nums[i]
8 nums[i], nums[j] = nums[j], nums[i]
9 else:
10 i += 1
11 for k in range(n):
12 if nums[k] != k:
13 return k
14 return n
15
16 # First Missing Positive (LC 41). Range is 1..n+1, find the smallest absent positive.
17 def first_missing_positive(nums):
18 n = len(nums)
19 i = 0
20 while i < n:
21 # Place nums[i] at index nums[i] - 1 if it is in range and not already there.
22 if 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
23 j = nums[i] - 1
24 nums[i], nums[j] = nums[j], nums[i]
25 else:
26 i += 1
27 for k in range(n):
28 if nums[k] != k + 1:
29 return k + 1
30 return n + 1
31
32 # Find All Duplicates (LC 442). Range is 1..n, each appears once or twice.
33 def find_duplicates(nums):
34 n = len(nums)
35 i = 0
36 while i < n:
37 if nums[i] != nums[nums[i] - 1]:
38 j = nums[i] - 1
39 nums[i], nums[j] = nums[j], nums[i]
40 else:
41 i += 1
42 return [nums[k] for k in range(n) if nums[k] != k + 1]Common Mistakes
- Advancing the pointer after every iteration instead of only when no swap was needed
- Forgetting to skip out-of-range or already-placed values (causes infinite loop)
- Using `nums[i] - 1 != i` as the swap guard instead of `nums[i] != nums[nums[i] - 1]` (the latter avoids re-swapping equal values)
- Mixing up 0-indexed (range 0..n) with 1-indexed (range 1..n) variants