Cyclic sort (1..n placement)

48 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

The list 3, 1, 5, 4, 2 holds each number from 1 to 5 exactly once, just shuffled. Sort it. Any sorting method works, but there is something special here: we know in advance where every number belongs. The number 3 belongs in slot 3, which is index 2 if we count from 0. The number v belongs at index v − 1.

By hand with that knowledge you would not compare anything. You would pick up the 3 from the first slot, walk to slot 3, put it there, and carry away whatever was sitting there. A general sort compares pairs and needs about n log₂ n steps; here we can do it with at most n moves and no extra paper.

The same knowledge answers questions without sorting: which number is missing from 1 to n, which one is duplicated, what is the smallest positive integer not present. Once every number is in its home slot, a slot holding the wrong number is the whole answer.

Build the structure, one piece at a time

The structure is the array itself, used as its own address book: index v − 1 is the home of value v.

Piece 1: a pointer i. Start at index 0.

Piece 2: the swap rule. Look at the value v at index i. If v is already home (v = i + 1), move on to i + 1. Otherwise swap it with whatever is at its home index v − 1, and stay at i, because a new value has just arrived there.

Three swaps and five advances. The name "cyclic" comes from the chain 3 → 5 → 2 → 1 that the first slot followed: each value displaced the next, around a cycle, until the cycle closed.

Piece 3: handling bad values. If a value is out of range (0, negative, or larger than n) or its home already holds a copy of it, there is nothing useful to do: advance. That is what makes the same loop work for finding a missing or duplicated number.

Why it is correct

The invariant: every index before i holds its home value, and no value that has been placed in its home is ever moved out again.

The second part is why it works: a swap only moves the value at i, which is not home (else we would have advanced), and the value at its home index, which cannot be the correct value there (else the home-already-holds-a-copy check would have fired). So each swap puts exactly one value in its home permanently, and the other value simply changes position without losing anything. We advance past index i only when it holds its home value, so the first part holds too.

When the loop ends, every index that could be satisfied is satisfied. If the input really was a permutation of 1 to n, the array is sorted. If one number was missing, its home slot holds the intruder, so a final scan for "index k does not hold k + 1" finds both the missing number (k + 1) and the extra one.

after the loop: array[k] = k + 1 for every k whose value is present; the first violation reveals the missing value

Why it is fast

Each swap places one value permanently, and there are only n values, so there are at most n swaps. Each advance moves i forward, so there are exactly n advances.

steps ≤ n swaps + n advances = 2n, so O(n) time and O(1) extra space

No comparisons between values, no extra array. For a million numbers, two million steps.

How to recognise it in an interview

The cue is a range: "numbers from 1 to n", "0 to n", or "in the range [1, n]", together with "missing", "duplicate", "first missing positive", and often "O(1) extra space". Say: "Every value has a known home index, so I swap each value into its home; then the slots that hold the wrong value are the answer."

First Missing Positive is the example loop with bad values skipped, then a scan for the first index k with array[k] ≠ k + 1. Find All Numbers Disappeared in an Array is the same scan reporting every violation. Find the Duplicate Number stops at the first swap where the home already holds the same value.

02The idea in one line

Swap each value into its home index until every slot holds its own number.

Reach for it when: Missing/duplicate numbers in 1..n, first missing positive.

Cost: O(n) time, O(1) space.

03The walk-through, step by step

The video works one example: Cyclic sort on [3,1,5,4,2]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Swap each value into its home index v − 1 until every slot is right
2. nums[0] = 3 belongs at index 2: swap
3. After the swap 3 sits at 2; keep working on index 0
4. nums[0] = 5 belongs at index 4: swap
5. After the swap 5 sits at 4; keep working on index 0
6. nums[0] = 2 belongs at index 1: swap
7. After the swap 2 sits at 1; keep working on index 0
8. nums[0] = 1 is already home: advance
9. nums[1] = 2 is already home: advance
10. nums[2] = 3 is already home: advance
11. nums[3] = 4 is already home: advance
12. nums[4] = 5 is already home: advance
13. Sorted in place: [1,2,3,4,5]
14. Each swap homes one value for good: O(n) time, O(1) space

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Sorting: Custom comparator / key sort, Quickselect (kth element), Merge sort with counting, Bucket / counting sort.