Cyclic Sort

Cyclic sort is an in-place array technique that runs in O(n) time and uses O(1) extra space. It’s tailor-made for interview questions where the array contains numbers from a known continuous range, most commonly 1..n or 0..n, because in those ranges every value has a natural “home index.” Instead of sorting by comparisons, you exploit structure by repeatedly placing values into the correct positions with swaps. Once the array is placed as correctly as possible, missing or duplicate values become easy to spot.

The core idea: value ↔ index mapping

The key insight is a simple mapping between values and indexes. When the valid range is 1..n and the array length is n, the value x belongs at index x - 1. When the valid range is 0..n, the value x belongs at the index x, but the value n does not fit in an array of length n (indexes only go 0..n-1), so it must be treated specially. This “value ↔ index” relationship is the signal that cyclic sort is likely the right tool.

When to use cyclic sort

You use cyclic sort when the problem constraints imply that values should line up with indexes, especially when the goal is to find an anomaly, such as a missing number, a duplicate, or a mismatch. Many problems that people initially solve with a hash set can often be solved in-place with cyclic sort, which is why it’s a common interview favorite whenever constant extra space is required.

How the algorithm works

The algorithm uses a pointer i that walks through the array, but it only moves forward when the current index is resolved. At the index i, you compute the correct index for the value currently sitting there. If the value isn’t in its home, you swap it with the element at its home index. After swapping, you do not advance i, because a new value has arrived at the position i and might also need to be moved. You keep swapping until either the correct value is in place or the current value can’t be moved further.

A helpful way to think about correctness is this invariant: before moving i forward, positions before i are already correct (or are duplicates that can’t be fixed any further). That’s why it’s safe to progress only when the current position is “done.”

Variant A: Range 1..n

In the 1..n version, the correct index for nums[i] is always nums[i] - 1. The most important safety check is to only swap when the swap will make progress: if nums[i] equals nums[correctIndex], you must stop swapping and move on. This check prevents infinite loops in arrays that contain duplicates, where two identical values would otherwise keep swapping back and forth.

Here is the standard pattern for the 1..n setup:

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

1 / 10

Variant B: Range 0..n

The 0..n variation is similar, but it needs a bounds guard because n is not a valid index inside an array of length n. In practice, that means you only swap values x when x < len(nums). If nums[i] == len(nums), you skip it and move forward. This variation appears frequently in “missing number” problems, where the missing value could be n.

A safe template for 0..n looks like this:

i = 0
while i < len(nums):
    if nums[i] < len(nums) and nums[i] != nums[nums[i]]:
        nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
    else:
        i += 1

After placement: How to detect anomalies

The real payoff comes after placement. Once the array is as correctly arranged as possible, you can scan it to reveal anomalies. In a 1..n array, the first index i where nums[i] != i + 1 immediately tells you that i + 1 is missing. In duplicate-related problems, you’ll often find that a “wrong” value is sitting in a position that belongs to a different number, which reveals both the duplicate and the missing value. In the 0..n missing-number problem, the first index i where nums[i] != i is the missing value; if all indexes match, then the missing value is n.

Why It’s O(n)

Even though the algorithm uses a while loop and repeated swaps, it remains O(n). Each swap places at least one element into its final position, and no element is permanently moved more than once. Since there are at most n elements to place, the total number of swaps is at most n, keeping the runtime linear. Since everything happens within the input array and uses only a few variables, the extra space remains O(1).

Common pitfalls

1. Incrementing i after a swap Don’t do it. You must re-check index i because a new number arrived there.
2. Wrong “correct index” formula For 1..n, it’s always nums[i] - 1.
3. Missing bounds check in 0..n problems If nums[i] == n, nums[i] is not a valid index—skip swapping.
4. Duplicates causing infinite loops Always ensure you only swap when nums[i] != nums[correct].

Interview signal checklist

If you see an array of length n containing numbers from 1..n or 0..nIf the question mentions missing values, duplicates, or extra space, a cyclic sort should be one of your first thoughts. It’s not just a sorting trick—it’s a placement strategy that turns a messy “missing/duplicate” problem into a clean index check.