cf.completefrontend
ARRAYS & HASHING · CORE

Cyclic sort

When the values are 1 to n, swap each value straight into its own slot, then any slot holding the wrong value reveals a missing or repeated number.

Time O(n)Space O(1) besides the output6 practice problemsStep-through picture

The idea

Some problems give an array of length n whose values all come from the range 1 to n. That's a strong hint: every value has a home. The value 1 belongs at index 0, the value 2 at index 1, and the value v at index v - 1.

Cyclic sort puts each value in its home by swapping. Look at index i. If the value there isn't already in its home, swap it into its home, which brings a new value to index i; look again. If it is home (or its home already holds the same value, a duplicate), move on to i + 1.

When it ends, scan the array once. Any index j that doesn't hold j + 1 shows that j + 1 is missing, and the value sitting there is a duplicate. All of this happens in place with no extra memory.

An everyday example

Returning library books to numbered slots

A shelf has slots numbered 1 to 10, and 10 books numbered 1 to 10 are put back in random order. You stand at slot 1 and look at its book. If it's book 7, you swap it with whatever is in slot 7, and now look at the book you got back. You keep swapping until slot 1 holds book 1 or holds a book whose slot is already correctly filled. Then you step to slot 2. Every swap puts at least one book in its final place, so it's quick. Any slot still holding the wrong book at the end tells you which book is missing.

How the example maps to the code
In the exampleIn the code
The slot you're standing ati
The slot where this book belongscorrect = nums[i] - 1
Swapping the book into its slot[nums[i], nums[correct]] = [nums[correct], nums[i]]
A slot holding the wrong book at the endnums[j] !== j + 1, so j + 1 is missing

From the slow way to cyclic sort

  1. Say the values should be 1 to n, some missing and some repeated. The obvious ways: check each number from 1 to n with a scan, which is O(n²); sort and then scan, O(n log n); or put everything in a Set, which is fast but uses O(n) extra memory.
  2. The range 1 to n matches the indexes 0 to n - 1 one to one. So the array itself can act as the set: if value v sits at index v - 1, the slot answers "is v present?". Each value has a home.
  3. Moving a value home is a swap: it goes to index v - 1, and whatever was there comes back to the current index. That newcomer may also be away from home, so check the same index again. Move on only when the value is home, or its home already holds a copy.
  4. After that, one scan finds every index j that doesn't hold j + 1, which means j + 1 is missing. Each swap follows a cycle of values pointing to each other's homes, which gives the method its name. That loop is cyclic sort.

How it works

  1. Start at i = 0.
  2. Work out where nums[i] belongs: correct = nums[i] - 1.
  3. If nums[correct] doesn't already hold that value, swap nums[i] and nums[correct]. Don't move i: a new value just arrived.
  4. Otherwise (the value is home, or its home already has a copy), move on: i++.
  5. When i reaches the end, every value that can be home is home.
  6. Scan once more: each index j where nums[j] !== j + 1 means j + 1 is missing.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function findMissing(nums) {
  2. let i = 0;
  3. while (i < nums.length) {
  4. const correct = nums[i] - 1;
  5. if (nums[i] !== nums[correct]) {
  6. [nums[i], nums[correct]] = [nums[correct], nums[i]];
  7. } else {
  8. i++;
  9. }
  10. }
  11. const missing = [];
  12. for (let j = 0; j < nums.length; j++) {
  13. if (nums[j] !== j + 1) missing.push(j + 1);
  14. }
  15. return missing;
  16. }

How fast it is

TimeO(n)
Extra memoryO(1) besides the output

Each swap puts one value home for good, so there are at most n swaps and n moves of i. Everything happens inside nums.

  • Best caseO(n)

    Already in place, like [1, 2, 3, 4]: no swaps, n moves of i, and one scan.

  • Average caseO(n)

    Some swaps and some moves, never more than 2n loop steps in all.

  • Worst caseO(n)

    Every value is away from home, like [2, 3, 4, 5, 1]: 4 swaps and 5 moves, 9 steps for 5 items.

Common mistakes

  • Moving i forward after a swap. The new value at i might also be out of place, and it gets skipped.
  • Checking i !== correct instead of comparing values, which loops forever on duplicates.
  • Forgetting the range check when values can be 0, negative, or larger than n, which reads outside the array.
  • Using it when you must not change the input. Copy the array first, or use a Set.

When to use it

Look for these clues in a problem:

  • The values are in the range 1 to n (or 0 to n) for an array of length about n.
  • The problem asks for missing numbers, duplicate numbers, or the smallest missing positive.
  • You must use O(1) extra space, so a Set isn't allowed.
  • You're allowed to change the input array.

Check yourself

Answer each one in your head first, then open it.

In the trace, how many times did the while loop run, and why can't it run more than 14 times?

10 times: 3 swaps and 7 moves of i. Each swap homes a value for good (at most 7) and i moves at most 7 times.

What does [2, 2, 2] return?

[1, 3]. No swaps happen, because each 2's home already holds a 2.

Why can a value at its home never be moved by a later swap?

A swap at index i moves only nums[i] and the value at nums[i] - 1. If that second value were home, it would equal nums[i], and the swap condition would be false.

After the sort, what does the value at a mismatched index tell you?

It is a repeat: its own home already holds a copy, which is why it was left at someone else's home.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 6 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

A value at its home never moves again. A swap happens only when nums[i] !== nums[correct]. The value at correct is then some w different from nums[i], sitting at index nums[i] - 1, which isn't w's home. So a swap never takes a value out of its home, and it always sends nums[i] into its home.

That gives the time bound. Each swap homes one more value for good, so there are at most n swaps. i goes up at most n times. The loop body runs at most 2n times, and the loop ends.

When the loop moves past index i, the value there has a copy at its home. Values at home stay put, and swaps never remove a value from the array, only move it. So at the end, every value present in the input sits at its home. Index j holds j + 1 exactly when j + 1 appears in the input, and the scan's list of mismatches is exactly the missing values.

Going deeper

3 more ideas

Why it takes linear time

The while loop looks like it could run forever, but every swap puts one value into its home, and a value at home is never moved again. So there are at most n swaps in total, plus n steps of i++. That's at most 2n iterations: O(n).

Why the check compares values, not indexes

The swap condition is nums[i] !== nums[correct], not i !== correct. With duplicates, the home of a duplicate already holds the same value. Comparing indexes would swap the two equal values forever. Comparing values sees that the home is taken and moves on.

Values outside the range

For "smallest missing positive", values can be 0, negative, or bigger than n. Those have no home, so add a range check: only swap when 1 <= nums[i] <= nums.length. Afterwards, the first index j with nums[j] !== j + 1 gives the answer j + 1, or n + 1 if every slot is right.

Work it by hand

Every step in a table, with why

Find the missing values among 7 numbers that should be 1 to 7. Two values are repeated.

nums = [2, 5, 2, 1, 4, 6, 6]

Stepinums[i]correctnums afterWhat happensWhy
1021[5, 2, 2, 1, 4, 6, 6]Swap: 2 goes homeIndex 1 holds 5, not 2, so they swap. Now 5 sits at index 0, and i stays put.
2054[4, 2, 2, 1, 5, 6, 6]Swap: 5 goes home5 belongs at index 4, which held 4. The 4 comes back to index 0.
3043[1, 2, 2, 4, 5, 6, 6]Swap: 4 goes home4 belongs at index 3. That brings 1 to index 0.
4010sameHome: i++1 is at its home, so the loop moves on. Three swaps have placed four values.
5121sameHome: i++2 was placed by the first swap.
6221sameCopy at home: i++This 2 belongs at index 1, which already holds a 2. It's a repeat, so it stays here.
7343sameHome: i++4 was placed by the third swap.
8454sameHome: i++5 was placed by the second swap.
9565sameHome: i++This 6 was already home from the start.
10665sameCopy at home: i++The second 6 finds a 6 at its home, so it stays. i becomes 7 and the loop ends.
11scan--[1, 2, 2, 4, 5, 6, 6]Missing: [3, 7]Index 2 holds 2 instead of 3, and index 6 holds 6 instead of 7. The values sitting there are the repeats.

It returns [3, 7]. The while loop ran 10 times, 3 swaps and 7 moves of i, within the limit of 2n = 14.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Cyclic sortO(n)O(1)Values are 1 to n (or close), you may reorder the input, and memory is limited.
Hash set of valuesO(n)O(n)The input must stay unchanged, or values don't fit a small range.
Sort, then scanO(n log n)O(1)The range doesn't match the indexes, but you can reorder and want little memory.
Sum or XOR of all valuesO(n)O(1)Exactly one number is missing and nothing repeats: the expected total minus the actual total is the answer.

Extra memory: O(1) besides the output: everything happens inside nums. The missing list can hold up to n - 1 values.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Cyclic sort and the other approaches, on a scale where each line up is 10 times more steps.
  • Cyclic sort, Hash set of values, Sum or XOR of all values O(n)
  • Sort, then scan O(n log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Cyclic sort101,0001 million
Hash set of values101,0001 million
Sort, then scan339,96620 million
Sum or XOR of all values101,0001 million

Inputs that need care

5 tricky inputs
An empty list: nums = []
Neither loop runs, and it returns [].
Nothing missing: nums = [3, 1, 2]
Two swaps sort it into [1, 2, 3], and the scan finds no mismatch, so it returns [].
All the same: nums = [2, 2, 2]
Every 2 finds a 2 at its home, so there are no swaps. The scan returns [1, 3].
A value out of range: nums = [1, 5, 2]
5 has no home among 3 slots. The swap writes nums[4], the array grows to length 5, and it returns the wrong answer [3, 4]. Only swap when 1 <= nums[i] <= nums.length.
The input must stay unchanged
Cyclic sort reorders nums. Copy it first with [...nums], which costs O(n) memory, or use a Set instead.

Variations and follow-ups

Twists interviewers add

Report the repeats

After the sort, each index j with nums[j] !== j + 1 holds a value that is a repeat. Collect nums[j] instead of j + 1, or both, to answer "which value is doubled and which is missing".

Mark with signs instead of swapping

For values 1 to n, make nums[Math.abs(v) - 1] negative for each value v. Indexes that stay positive are missing values. This also uses O(1) space and changes the input, but restoring the signs afterward is easy.

Values from 0 to n

If values run from 0 to n in an array of n items, the home of v is index v, and the value n has no home. Skip it during the swaps, and the scan finds the one missing number.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "values in the range 1 to n", "array of length n", "find the missing or duplicate numbers", and "constant extra space".
  • Explain the homes first: "value v belongs at index v - 1". Then the swap rule and the final scan follow naturally.
  • Test by hand: a list already in place, a list where every value is the same, and one with values far from home.
  • A common follow-up is "what if you can't change the input?". Answer: use a Set, or for a single duplicate in values 1 to n, treat values as links between indexes and find the cycle with fast and slow pointers.

Where frontend code uses it

The same idea in real UI code
  • Finding which numbered chunks of a large file upload never arrived, when chunks are numbered 1 to n.
  • Spotting gaps in sequence numbers of messages received over a WebSocket, to request the missing ones again.
  • Checking which page numbers are missing from a paginated fetch that should have returned pages 1 to n.

Related algorithms