Cyclic Sort Interview Pattern: Missing and Duplicate Numbers in O(n)
Some interview problems look like they need a hash set or a sort, but the interviewer then asks for O(n) time and O(1) extra space. When the input is an array of numbers in a known range, like 1 to n or 0 to n, that follow-up usually points to one idea: cyclic sort.
This guide explains the cyclic sort interview pattern, how to recognize it, the core loop, and how to talk through it clearly.
How to recognize the pattern
Look for these signals:
- The array contains integers in a fixed range, typically
1..nor0..n. - The question asks about missing, duplicate, or misplaced numbers.
- There's a constraint like "constant extra space" or "modify the array in place."
Classic examples:
- Find the missing number in
0..n. - Find all numbers that disappeared in an array of
1..n. - Find the duplicate number.
- Find all duplicates.
- First missing positive integer.
The core idea
If the values are in the range 1..n, each value has a "home" index: value v belongs at index v - 1. Cyclic sort walks through the array and keeps swapping the current value into its home until the current position holds the right value, or holds a value that can't be placed.
def cyclic_sort(nums):
i = 0
while i < len(nums):
correct = nums[i] - 1
if nums[i] != nums[correct]:
nums[i], nums[correct] = nums[correct], nums[i]
else:
i += 1
return nums
Why it's O(n): every swap puts at least one number in its final place. There can be at most n such placements, so the total number of swaps is bounded by n, even though there's a loop inside a loop in spirit.
Why compare values, not indices: checking nums[i] != nums[correct] instead of i != correct prevents infinite loops when there are duplicates. If the home slot already holds the same value, we move on.
Example 1: Find all missing numbers in 1..n
After cyclic sort, any index i where nums[i] != i + 1 is a spot whose rightful value is missing.
def find_disappeared(nums):
i = 0
while i < len(nums):
correct = nums[i] - 1
if nums[i] != nums[correct]:
nums[i], nums[correct] = nums[correct], nums[i]
else:
i += 1
return [i + 1 for i in range(len(nums)) if nums[i] != i + 1]
Example 2: Find the duplicates
Same sort; now the value sitting in a wrong spot is the duplicate.
def find_duplicates(nums):
i = 0
while i < len(nums):
correct = nums[i] - 1
if nums[i] != nums[correct]:
nums[i], nums[correct] = nums[correct], nums[i]
else:
i += 1
return [nums[i] for i in range(len(nums)) if nums[i] != i + 1]
Example 3: First missing positive
Here the array can contain negatives, zeros, and numbers larger than n. The trick is to only place values that fall in 1..n and ignore the rest.
def first_missing_positive(nums):
n = len(nums)
i = 0
while i < n:
v = nums[i]
if 1 <= v <= n and nums[v - 1] != v:
nums[i], nums[v - 1] = nums[v - 1], nums[i]
else:
i += 1
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
This is a well-known hard problem, and cyclic sort turns it into a short, explainable solution.
Talk track for the interview
- Name the range observation: "The values are between 1 and n, so each value has a natural index."
- Explain the placement: "I'll swap each number into its home index until the current slot is settled."
- Justify complexity: "Each swap fixes at least one element, so total swaps are at most n. Time is O(n), extra space O(1)."
- Explain the scan: "After placement, any index that doesn't hold its value tells me what's missing or duplicated."
- Mention the trade-off: "This modifies the input. If that's not allowed, I'd use a hash set with O(n) space, or restore the array afterward."
Common bugs
- Off-by-one homes. For
0..n, the home ofvis indexv, and valuenhas no slot. Decide how to handle it before coding. - Infinite loops with duplicates. Compare values at the two positions, not the indices.
- Incrementing i after a swap. Don't. The new value at
istill needs checking. - Forgetting out-of-range values in first-missing-positive.
Related alternatives worth mentioning
- Sum or XOR tricks for a single missing number in
0..n: O(n) time, O(1) space, no mutation. - Sign marking: flip
nums[abs(v) - 1]negative to mark "seen." Also O(1) space but also mutates the input. - Floyd's cycle detection for "find the duplicate" when you can't modify the array.
Mentioning one of these shows you understand the space of solutions, not just one template.
Practice the explanation, not just the code
Cyclic sort is short to write but easy to fumble when nervous, especially the loop condition. Luna Interview helps you rehearse explaining patterns like this out loud and under time pressure, so the reasoning comes out clearly in the real round.
Solve the five classic problems above twice each, saying the talk track out loud, and this pattern will stick.
Rehearse with an AI interview copilot, then browse commonly reported interview questions.