Cyclic Sort Pattern: Solving Missing-Number Questions in O(n)

TL;DR: When an array holds numbers drawn from a known range, every value already knows which index it belongs at. Swap each one home in a single pass, then scan for the position holding the wrong value, and that position names the missing number, the duplicate, or the corrupt pair. The whole family runs in O(n) time and O(1) space, which is exactly why interviewers attach the phrase "without extra space" to these questions: it removes the hash set and forces this pattern. One swap loop covers all of it, and one comparison inside that loop decides whether your solution terminates.

This is the fourteenth deep dive in our pattern series (the full map lives in the hub), following trie. Cyclic sort is the smallest pattern in the series and one of the most mechanical, which is precisely why it is worth twenty minutes: the tell is nearly impossible to miss once you know it, the code is eight lines, and candidates who have not seen it reliably burn the interview reaching for sorting or a hash set that the constraints have already ruled out.

The tell: how to recognize a cyclic sort problem

This pattern has the most literal tell on the list. Suspect it when the question describes an array containing numbers from a known, contiguous range:

• "an array of n numbers taken from the range 1 to n"
• "containing numbers from 0 to n"
• "find the missing number" or "find all missing numbers"
• "find the duplicate" or "find all duplicates"
• "find the corrupt pair" (one number replaced by another)
• "the smallest missing positive number"

Then look for the constraint that turns it from optional into required: "in O(n) time and O(1) extra space". That sentence removes sorting (O(n log n)) and removes the hash set (O(n) space), and what remains is this pattern.

If the range phrase is absent, the pattern does not apply. That is a genuinely useful negative: cyclic sort is not a general-purpose sorting technique, it is a trick that works only because the values and the indices come from the same set.

The one insight the whole pattern rests on

Here is the sentence that is the pattern: when the values are 1 to n, the value v belongs at index v - 1, so every number tells you where it should live.

Ordinary sorting has to compare elements to discover the order. Here there is nothing to discover. A 5 belongs at index 4, always, regardless of what else is in the array. So you can place values directly rather than comparing, and placement is what makes it linear.

Once every value that has a home is sitting in it, the array reads as 1, 2, 3, ... except at the positions where something is wrong. Scan once, and the first index whose value is not index + 1 is the answer to whichever question was asked. Missing number, duplicate, corrupt pair: same sort, different scan.

The template

def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        correct = nums[i] - 1                       # where nums[i] belongs
        if nums[i] != nums[correct]:                # compare VALUES
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1                                  # settled, or a duplicate
    return nums

nums[i] != nums[correct] rather than i != correct is the detail the pattern lives on. Both look like they say "this value is not home yet". They differ when the array contains a duplicate: with i != correct, two equal values keep swapping with each other forever and the loop never ends. Comparing the values themselves means a swap only happens when it makes progress, and a duplicate simply causes i to advance. Whenever a cyclic sort solution hangs, this is why.

Note that i only advances in the else branch. That is intentional: after a swap, the value now sitting at i is new and has not been placed yet, so you must examine the same index again.

Why this is O(n) despite a loop containing swaps. Every swap puts at least one value into its final position, permanently. A value that reaches its home is never moved again, so there can be at most n swaps across the entire run. Add at most n increments of i and the total work is bounded by 2n. This is the same amortized argument as the monotonic stack scan, and interviewers grade it the same way, so say it out loud rather than hoping the code speaks for itself.

Then the scan, which is where each variant differs:

def find_missing_number(nums):
    """nums holds n values drawn from 1..n, so something missing implies something repeated."""
    cyclic_sort(nums)
    for i in range(len(nums)):
        if nums[i] != i + 1:
            return i + 1                            # this slot's owner never arrived
    return len(nums) + 1                            # everything present, so n+1

Read that docstring carefully, because it is a real precondition rather than a comment. This scan assumes the array length matches the value range, which is the case for Find All Numbers Disappeared in an Array, where duplicates take the place of the missing values. LeetCode's Missing Number is the other convention (n values drawn from 0 to n), and passing that input to the loop above would try to send the value n to index n, which does not exist. The next section handles that.

For "find all missing", collect every mismatched index instead of returning the first. For "find all duplicates", collect nums[i] at every mismatched index, because the value squatting in the wrong slot is the extra copy. For a corrupt pair, return both. Same sort, three scans.

Mind the two index conventions

Half of these problems use the range 1 to n and half use 0 to n. They need different arithmetic:

• Values 1 to n: value v belongs at index v - 1. Use correct = nums[i] - 1.
• Values 0 to n-1: value v belongs at index v. Use correct = nums[i].
• Values 0 to n (Missing Number, where one of n+1 possible values is absent): the range is wider than the array, so the value n has no home and must be skipped rather than placed.

That last case is the one that throws an index error if you reuse the plain loop, so it gets its own guard:

def missing_number(nums):
    """nums holds n distinct values drawn from 0..n, so exactly one is absent."""
    n = len(nums)
    i = 0
    while i < n:
        correct = nums[i]                           # value v belongs at index v
        if correct < n and nums[i] != nums[correct]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1                                  # settled, or the homeless value n
    for i in range(n):
        if nums[i] != i:
            return i
    return n                                        # 0..n-1 all present, so n is missing

The added correct < n is the whole difference. Write down which convention the problem uses before you write the loop. Deriving it mid-code is where the off-by-one errors come from.

Want the whole family taught in order? The cyclic sort chapter of Grokking the Coding Interview builds from the basic placement loop through the duplicate and corrupt-pair variants up to First Missing Positive, with worked traces and code in six languages, then does the same for all 42 patterns (32 common + 10 advanced).

The compass: cyclic sort against the alternatives

Interviewers usually let you propose a simpler approach first, then add the constraint that kills it. Have the comparison ready:

• Hash set: O(n) time, O(n) space, works for every variant. It is the correct first answer, and the space constraint is what rules it out.
• XOR trick: O(1) space, but it only handles exactly one missing or one duplicate value. It cannot find all missing numbers, and it cannot report a corrupt pair.
• Sorting: O(n log n), which fails the time requirement, and it also destroys the input.
• Cyclic sort: O(n) time, O(1) space, and it handles every variant including "find all". It does modify the input, which is worth flagging if the problem forbids that.

That last caveat matters. Find the Duplicate Number specifically states that the array must not be modified, and that single sentence moves the problem out of this pattern and into fast and slow pointers, where the array is treated as a linked list and the duplicate is the cycle entrance. Noticing that switch is exactly the kind of reading interviewers reward.

The three mistakes that sink candidates

1. Comparing indices instead of values. while i != correct loops forever the moment a duplicate exists. Compare nums[i] with nums[correct], every time.

2. Advancing i after a swap. The value swapped into position i is unexamined. Only increment when the current index is settled, which means only in the else branch.

3. Not guarding out-of-range values. In First Missing Positive the input is arbitrary: it can hold negatives, zeros, and numbers far larger than n. Those have no home index, so skip them rather than computing an index from them. Forgetting the guard produces an index error on the first negative number.

The variant that looks harder and is not

First Missing Positive is marked hard and is the same pattern with one added observation: with n slots, the smallest missing positive integer is at most n + 1. So anything outside the range 1 to n cannot be the answer and can be ignored during placement. Run the same loop with a range guard, scan for the first mismatch, and return n + 1 if there is none. Recognizing that bound is the entire difficulty, and it comes directly from the pattern's core idea.

Practice ladder

In order, each rung adding one wrinkle.

1. Missing Number (E): the 0 to n convention.
2. Find All Numbers Disappeared in an Array (E): collect every mismatch instead of the first.
3. Set Mismatch (E): the corrupt pair, returning both values.
4. Find All Duplicates in an Array (M): read the squatting value rather than the index.
5. Find the Duplicate Number (M): read the constraints, then notice the array cannot be modified and switch patterns.
6. First Missing Positive (H): the range guard and the n + 1 bound.

Then write the tell in your own words ("I should suspect cyclic sort when ___") and move on. Recognition, not volume, is the skill.

The takeaway

One precondition (values drawn from a known contiguous range), one idea (each value knows its own index, so place rather than compare), one comparison that decides whether the loop terminates (values, not indices), one argument worth saying out loud (at most n swaps, so O(n)), and one boundary (if the input must not be modified, this is a different pattern). The full map of where this sits among the other 41 patterns is in the complete pattern guide. Next in the series: Matrix Traversal, where a grid turns out to be a graph.

Go deeper: Grokking the Coding Interview teaches all 42 patterns (32 common + 10 advanced) across 300+ sequenced problems, for a one-time $79 with lifetime access. Short on time? Grokking 75 includes the essential cyclic sort problems in its 6-week plan.

FAQs

What is cyclic sort in simple terms? A way to sort an array whose values come from a known range, by putting each value directly at the index it belongs to instead of comparing elements. Because placement needs no comparisons, the whole pass runs in linear time and uses no extra memory.

Why does the swap condition compare values instead of indices? Because duplicates break the index version. If two positions hold the same value, i != correct stays true forever and they swap endlessly. Comparing nums[i] with nums[correct] means a swap only happens when it actually places a new value, so duplicates simply let the loop move on.

Why is cyclic sort O(n) when it has a loop with swaps inside? Every swap sends at least one value to its permanent home, and a settled value is never moved again, so there are at most n swaps in total. Adding at most n increments of the index gives a bound of about 2n operations regardless of the input order.

When should I use a hash set instead? When there is no constraint on extra space. A hash set is simpler, does not modify the input, and solves every variant in linear time. Cyclic sort exists for the case where the problem explicitly demands constant extra space.

Is the cyclic sort pattern asked at FAANG companies? Yes, mostly as Missing Number, Find All Duplicates, and First Missing Positive. It shows up more often in phone screens than in onsite rounds, because it is a fast way to check whether a candidate recognizes a constraint and picks the technique it points to.