Cyclic Sort Pattern

Why Index Placement Works

Cyclic sort is not really about sorting for presentation. It is about using the array itself as a lookup table. The pattern appears when values are supposed to come from a tight range like 0..n or 1..n. In that world, each value has a natural home: value v belongs at index v or v-1. If you can place values directly into those homes, any mismatch that remains tells you exactly what information is missing or duplicated.

The reason this works in linear time is subtle but important. A swap is not random churn. Every successful swap places at least one number into its correct position. That means the total number of productive swaps across the whole algorithm is bounded by n. You may stay on the same index for several iterations, but each repeat fixes another misplaced value, so the total work still stays linear.

Unlike comparison-based sorting, cyclic sort exploits the meaning of the values. It would be useless on arbitrary integers because those values do not map neatly to valid indices. But when a problem says “numbers are from 1 to n” or “one number is missing from 0 to n,” that range guarantee is the invitation. The array becomes both storage and bookkeeping structure at the same time.

Another strength of the pattern is that it exposes more than one kind of anomaly. If a value cannot reach its home because its home already contains the same value, you found a duplicate. If a slot ends the process holding the wrong number, the missing value is tied directly to that slot index. The same placement mechanism reveals different outputs depending on what the question asks you to report.

Walkthrough

Consider nums = [3,4,1,5,2], where the values should be 1..5. Index 0 should hold 1, but it currently holds 3. The correct home for 3 is index 2, so swap nums[0] with nums[2]. The array becomes [1,4,3,5,2]. Stay on index 0: now it already holds the correct value 1, so move to index 1.

At index 1, the value is 4, whose home is index 3. Swap to get [1,5,3,4,2]. Index 1 still is not correct, because now it holds 5, whose home is index 4. Swap again and get [1,2,3,4,5]. Now index 1 is correct too, and the remaining indices already line up. The whole array is fixed after only a few swaps because each swap places some number closer to, or directly into, its home.

The interesting case is when duplicates exist. Suppose nums = [4,3,2,7,8,2,3,1]. During placement, a value sometimes wants to go into a slot that already contains that same value. You must stop swapping in that situation or you will loop forever. That duplicate collision is itself meaningful: one copy occupies the rightful home, and the extra copy proves some other value is missing elsewhere.

Implementation

The implementation pattern is a for i < len(nums) loop, not a simple for range. You only advance i when the current slot is resolved. If the value is valid and belongs somewhere else, swap it into its home and re-check the same index because a new value just arrived there.

From that helper, many interview solutions become tiny. For “find the first missing positive,” place all positive in-range numbers where they belong, then scan for the first index i where nums[i] != i+1. For “find all missing numbers,” collect every mismatched index after placement. For “find the duplicate,” notice which value tried to occupy an already-occupied home.

When Cyclic Sort Does Not Fit

Do not force cyclic sort onto every missing-number question. The pattern depends on three conditions: values correspond to a small indexable range, modifying the array is allowed, and you can afford in-place swaps. If the values are huge, sparse, or the input must remain unchanged, another technique is better. XOR, arithmetic sums, sets, or Floyd's cycle detection may solve those variants more naturally.

• Look for ranges like 1..n or 0..n.
• Ask whether in-place mutation is allowed.
• Use position mismatch as the final signal for missing or duplicate values.
• Watch for duplicate collisions before swapping.

In an interview, the best explanation is concrete: “Each number has a home index. I keep swapping until the current index contains either the right number, an out-of-range value, or a duplicate already sitting in its home. After that, any remaining mismatch directly answers the question.” That shows both the mechanism and the stopping rule.

Practice Problems

Quiz