Cyclic Sort

When an array holds numbers from 1 to n, each value has a home index. Swap every value home in O(n) time and O(1) space, then read the missing and duplicate numbers off the indexes that do not match.

Overview

The idea

Suppose an array of length n holds numbers from the range 1 to n. Then the value v has a natural home: index v - 1. If every number appeared exactly once, the sorted array would be [1, 2, 3, ..., n], with each value sitting at its home. Cyclic sort puts every value that can go home there by swapping, in one pass, without any extra memory. The array acts as its own hash table.

It tests whether you notice the range constraint. A hash set solves missing-number and duplicate questions in O(n) time but O(n) space; sorting takes O(n log n). Cyclic sort gets O(n) time and O(1) extra space, and the questions almost always ask for exactly that.

Notice that after a swap the index does not move. A new value has just arrived at i, and it may need to go home too.

A trace

Run it on [3, 1, 5, 4, 2]. The home of 3 is index 2, the home of 1 is index 0, and so on.

1 — 0 — 3 — 2 — swap indexes 0 and 2 — 5, 1, 3, 4, 2
2 — 0 — 5 — 4 — swap indexes 0 and 4 — 2, 1, 3, 4, 5
3 — 0 — 2 — 1 — swap indexes 0 and 1 — 1, 2, 3, 4, 5
4 — 0 — 1 — 0 — home, i += 1 — 1, 2, 3, 4, 5
5 — 1 — 2 — 1 — home, i += 1 — 1, 2, 3, 4, 5
6 — 2 — 3 — 2 — home, i += 1 — 1, 2, 3, 4, 5
7 — 3 — 4 — 3 — home, i += 1 — 1, 2, 3, 4, 5
8 — 4 — 5 — 4 — home, i += 1 — 1, 2, 3, 4, 5

Three swaps sorted the array, all of them while i stayed at 0. Each swap sent one value home for good: first 3, then 5, then 2, and the last swap also brought 1 home.

Why it is O(n)

The loop has a loop inside it, which looks like O(n²). Count the two kinds of step separately.

swap — puts one value at its home, where it never moves again — n
advance — moves i one place to the right — n

A value at its home is never swapped out: the only swap that touches index v - 1 is one that brings v there, and v is already there. So each swap settles a new value, and there can be at most n swaps. The trace above took 8 steps, 3 swaps and 5 advances, and no input of length 5 can take more than 10.

Duplicates and values outside the range

Two inputs break the naive version. A duplicate makes the swap loop spin forever: on [3, 1, 2, 5, 2], the pass reaches [1, 2, 3, 2, 5] with i at index 3, where the value 2 has its home, index 1, already holding a 2; swapping the two copies changes nothing, so a loop without the check never advances. A value outside 1 to n, such as -1 or n + 5, has no home at all. The check in the flowchart handles both: skip a value that is out of range, and skip a value whose home already holds a copy of it.

1 — 0 — 3 — home is index 2, swap — -1, 4, 3, 1
2 — 0 — -1 — out of range, i += 1 — -1, 4, 3, 1
3 — 1 — 4 — home is index 3, swap — -1, 1, 3, 4
4 — 1 — 1 — home is index 0, swap — 1, -1, 3, 4
5 — 1 — -1 — out of range, i += 1 — 1, -1, 3, 4
6 — 2 — 3 — home, i += 1 — 1, -1, 3, 4
7 — 3 — 4 — home, i += 1 — 1, -1, 3, 4

That is Smallest Missing Positive on [3, 4, -1, 1]. After the pass, index 1 does not hold 2, so the answer is 2. If every index had matched, the answer would be n + 1.

The second pass

The placement pass is the same for every problem in this family. The problems differ only in what the mismatches mean afterward.

Find Missing Number — n distinct values from 0 to n — index v (n has no slot) — i is missing; if none, n is missing
Find All Missing Numbers — 1 to n, with repeats — index v - 1 — i + 1 is missing
Find Corrupt Pair — 1 to n, one repeat — index v - 1 — nums[i] is the duplicate, i + 1 is missing
Smallest Missing Positive — anything — index v - 1 if 1 ≤ v ≤ n — the first mismatch i gives i + 1; else n + 1
Find all duplicates — 1 to n, with repeats — index v - 1 — nums[i] is a duplicate

Find Corrupt Pair on [3, 1, 2, 5, 2] ends as [1, 2, 3, 2, 5]: index 3 holds 2 instead of 4, so the duplicate is 2 and the missing number is 4.

Find Missing Number uses the range 0 to n, so value v lives at index v and the value n has no slot. Treat n like an out-of-range value: leave it where it is. If the pass ends with every index i holding i, the missing number is n.

Finding the duplicate without changing the array

Find Duplicate Number adds two rules: n + 1 values from 1 to n, exactly one value repeated, and the array must not be modified. Cyclic sort would rearrange it, so that is out. Read each value as a pointer instead: index i points to index nums[i]. Because every value is between 1 and n, every pointer lands inside the array, and starting from index 0 the walk never stops. Since the array has n + 1 slots but only n distinct targets, two indexes point to the same place, and that place is the repeated value: the walk enters a cycle there.

Floyd's cycle detection finds the cycle entrance with two pointers and O(1) space. A slow pointer moves one step and a fast pointer two until they meet; then a new pointer from the start and the slow pointer move one step each, and where they meet is the entrance.

start — 1 — 1
step 1 — 3 — 2
step 2 — 2 — 2, met
phase 2, start — 1 (from the start) — 2 (from the meeting point)
phase 2, step 1 — 3 — 4
phase 2, step 2 — 2 — 2, met

The duplicate is 2. This is the same algorithm as Linked List Cycle II, which is why the problem belongs to two topics.

Alternatives, and when each wins

hash set — O(n) — O(n) — none
sort, then scan — O(n log n) — depends on the sort — changes the array
sum formula, n(n + 1) / 2 minus the total — O(n) — O(1) — one missing number only; watch fixed-width overflow
XOR of indexes and values — O(n) — O(1) — one missing number only
cyclic sort — O(n) — O(1) — values in a known range; changes the array
Floyd's cycle — O(n) — O(1) — one duplicate; the array must not be changed

Cyclic sort is the general tool of the family: it finds several missing or duplicate numbers at once. The sum and XOR tricks are shorter when exactly one number is missing.

How to spot it

values from 1 to n, or 0 to n, in an array of about n elements — each value has a home index
find the missing, duplicate or corrupt numbers, O(1) extra space — cyclic sort, then scan for mismatches
smallest missing positive, any values — ignore values outside 1 to n, then cyclic sort
one duplicate, array must not change — Floyd's cycle on the values as pointers
values with no bound — a hash set; cyclic sort does not apply

What you will be able to do

Explain why values in 1 to n give the array a hash table for free.
Write the placement loop with the two skips that prevent an infinite loop.
Prove the O(n) bound by counting swaps and advances separately.
Read missing numbers, duplicates and corrupt pairs off the mismatches.
Switch to Floyd's cycle detection when the array must not be modified.

When to use it

The array holds numbers from 1 to n or 0 to n and has about n elements
Finding one missing number, or all of them, in O(1) extra space
Finding duplicates in O(1) extra space, when the array may be rearranged
Finding the corrupt pair: the value that appears twice and the value it replaced
Smallest missing positive in an unsorted array with arbitrary values
Any question where values map directly to indexes and the follow-up is to drop the hash set

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio