Cyclic Sort

Whenever a problem hands you an array containing numbers from a known range — typically 1..n or 0..n-1 — and asks you to find a missing or duplicate value without extra space, that range is the cue. Cyclic sort exploits it directly: if the array truly held every number 1..n exactly once, number v would belong at index v - 1. So just put it there.

What you’ll learn

• The cyclic-sort swap: place each number at its “home” index in one pass.
• Why this runs in $O(n)$ time despite a nested-looking while inside the for.
• Worked example: finding the missing number in a 0..n range.
• The variant for finding a duplicate without a set.
• The cue: “numbers from 1 to n” (or “0 to n”), “find missing/duplicate”, “O(1) extra space.”

The cue

You are looking at cyclic sort when…

• The problem states the values are a permutation of 1..n (or 0..n-1), possibly with one missing, one duplicated, or a few swapped.
• And it asks for $O(n)$ time with $O(1)$ extra space — which rules out both a hash set and a sort.

That range constraint is not decoration; it is the entire algorithm. When the values are exactly 1..n, every value has one correct home — index v - 1 — so sorting needs no comparisons at all, only placement. The array becomes its own lookup table.

Reach for something else when values can repeat arbitrarily, are unbounded, or are not integers. Without the 1..n promise there is no home to send a value to, and you are back to a hash map or a sort.

The pattern

Walk the array with index i. While the value at i isn’t already in its home position, swap it there. Each swap places at least one number correctly, so the whole array sorts itself in a single pass over all the swaps.

cyclic_sort_template.py

def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        correct_index = nums[i] - 1     # where nums[i] belongs, for values 1..n
        if nums[i] != nums[correct_index]:
            nums[i], nums[correct_index] = nums[correct_index], nums[i]
        else:
            i += 1                      # nums[i] is already home, move on
    return nums
 
 
print(cyclic_sort([3, 1, 5, 4, 2]))   # expect [1, 2, 3, 4, 5]

How it works

The outer index i only advances when the value sitting there is already correct. Every swap sends exactly one number to its final home, and a number is never swapped out of its home position once it’s there — so across the whole array, there are at most n swaps total, keeping the pass $O(n)$ even though it looks like a loop inside a loop.

sketch Cyclic sort: swapping each number to its home index p5.js Pause Restart

Value v belongs at index v-1. Each swap sends one number home; i only advances once the value at i is already correct.

Worked example

Missing Number. Given n distinct numbers from 0 to n with exactly one missing, cyclic sort each value to index value (adjusting for the 0..n range instead of 1..n), then scan for the first index that doesn’t hold its own index.

missing_number.py

def missing_number(nums):
    i = 0
    n = len(nums)
    while i < n:
        correct_index = nums[i]
        if nums[i] < n and nums[i] != nums[correct_index]:
            nums[i], nums[correct_index] = nums[correct_index], nums[i]
        else:
            i += 1
 
    for i in range(n):
        if nums[i] != i:
            return i
    return n   # every index 0..n-1 was correct -- n itself is missing
 
 
print(missing_number([3, 0, 1]))       # expect 2
print(missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1]))   # expect 8

Find the Duplicate Number. Numbers 1..n in an array of size n + 1 guarantee at least one duplicate. Cyclic-sort each value toward index value - 1; the swap that fails because the target slot already holds the same value reveals the duplicate directly.

find_duplicate.py

def find_duplicate(nums):
    i = 0
    while i < len(nums):
        if nums[i] != i + 1:
            correct_index = nums[i] - 1
            if nums[i] != nums[correct_index]:
                nums[i], nums[correct_index] = nums[correct_index], nums[i]
            else:
                return nums[i]      # this value is already home -- it's the duplicate
        else:
            i += 1
    return -1
 
 
print(find_duplicate([1, 4, 4, 3, 2]))   # expect 4

Find All Numbers Disappeared in an Array

Same cyclic-sort pass as Missing Number, but for 1..n values in an array of size n where multiple numbers can be missing: after sorting, every index i whose value isn’t i + 1 marks a missing number i + 1. One pass to sort, one pass to collect — still $O(n)$ time and $O(1)$ extra space (besides the output list).

Time and space complexity

Approach	Time	Space
Hash set of seen values	$O(n)$	$O(n)$
Sort the array first, then scan	$O(n \log n)$	$O(1)$ to $O(n)$
Cyclic sort	$O(n)$	$O(1)$

Cyclic sort matches the hash-set approach’s time complexity while using none of its extra memory — the swap-in-place is what makes that possible, and it only works because the values are known to fall in a tight 1..n (or 0..n) range.

When to use it

Cue in the problem	Why cyclic sort fits
“array contains numbers from 1 to n” (or 0 to n)	Each value has a known home index
“find the missing number”	Sort, then scan for the first index mismatch
“find the duplicate number”	A swap fails because the target already holds the same value
“find all missing/duplicate numbers”	Sort once, then a linear scan reports all mismatches
“do it in O(1) extra space”	Cyclic sort mutates the input array in place

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output — then paste the same code into leetcode.com.

LC 268 — Missing Number · Easy

Problem. Given an array containing n distinct numbers drawn from [0, n], return the one number that is missing.

Constraints. n == len(nums), 1 <= n <= 10^4, all values distinct and in range. Can you do it in $O(n)$ time and $O(1)$ space?

Examples. [3,0,1] gives 2 · [0,1] gives 2 · [9,6,4,2,3,5,7,0,1] gives 8

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The values are a permutation of [0, n] with one omission, so pairing each index with the value at it leaves exactly one unmatched number. XOR performs that pairing because $x \oplus x = 0$.

Time $O(n)$. Space $O(1)$.

Seeding with len(nums) matters: indices run 0..n-1 but values run 0..n, so the index n must be contributed manually.

[0] giving 1 and [1] giving 0 are the two single-element cases, and they are the ones a formula written from memory tends to get backwards.

The arithmetic alternative, n * (n + 1) // 2 - sum(nums), is equally $O(n)$ and arguably clearer. XOR’s advantage is that it cannot overflow — irrelevant in Python, decisive in C++ or Java with large n. Mentioning that is the reason to prefer it. See Bitwise XOR Patterns.

Follow-ups you should expect: “Two numbers missing?” — the sum and sum-of-squares give two equations, or partition by a differing bit as in LC 260. “Values 1..n instead of 0..n?” — shift the pairing by one. “Find the duplicate instead (LC 287)?” — values 1..n with one repeat and a read-only array, so use fast and slow pointers on the index graph. “Cyclic-sort version?” — place each value at its index, then scan for the mismatch; same $O(n)$, but it mutates the input.

LC 448 — Find All Numbers Disappeared in an Array · Easy

Problem. Given an array of n integers where each value is in [1, n], return all the values in that range which do not appear. Aim for $O(n)$ time and no extra space (the output does not count).

Constraints. 1 <= n <= 10^5, 1 <= nums[i] <= n.

Examples. [4,3,2,7,8,2,3,1] gives [5,6] · [1,1] gives [2] · [1] gives []

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Because every value lies in [1, n], value v has a natural home at index v - 1. That lets the array double as a presence table, with the sign bit as the marker — no extra space required.

Time $O(n)$, two passes. Space $O(1)$ beyond the output.

Two details:

• abs(n) when reading. A slot may already have been negated by an earlier value, and using the negative directly would compute the wrong index.
• if nums[idx] > 0 before negating. Duplicates would otherwise flip a slot twice, turning it positive again and reporting a present value as missing. [1,1] is the minimal test: without the guard, index 0 is negated twice and 1 is wrongly reported missing.

[2,2] giving [1] is the same trap from the other direction.

If mutating the input is unacceptable, a set of the values is $O(n)$ space and perfectly fine — state the trade rather than assuming in-place is required.

Follow-ups you should expect: “Find the duplicates instead (LC 442)?” — same marking, but report values whose slot was already negative. “Both missing and duplicated (LC 645)?” — one pass gives both. “Restore the array afterwards?” — a third pass taking abs of everything. “Do it with cyclic sort?” — swap each value to its home index, then scan for mismatches; also $O(n)$ and also destructive.

LC 41 — First Missing Positive · Hard

Problem. Given an unsorted array, return the smallest positive integer that is not present. You must run in $O(n)$ time and use $O(1)$ auxiliary space.

Constraints. 1 <= len(nums) <= 10^5, -2^31 <= nums[i] <= 2^31 - 1.

Examples. [1,2,0] gives 3 · [3,4,-1,1] gives 2 · [7,8,9,11,12] gives 1

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The key observation is a bound on the answer: with n slots, the values 1..n either all appear — making the answer n + 1 — or one of them is missing. So nothing outside 1..n needs storing, and the array itself has exactly enough room to record which of those values are present.

Place each in-range value at index value - 1, then the first index whose content disagrees with its position reveals the gap.

Time $O(n)$. Each swap places at least one value permanently at its home, so across the whole run there are at most n swaps — the while does not make it quadratic. Space $O(1)$.

Three details, each with a test case:

• while, not if. The value swapped into position i may itself be misplaced and must be processed before moving on.
• Compare values, not indices. The guard is nums[nums[i] - 1] != nums[i]. Writing it as an index comparison loops forever on duplicates — [1,1] is the minimal case, and it must return 2.
• Out-of-range values are left alone. Negatives and values above n fail the range check and stay put, which is correct since they cannot be the answer.

[7,8,9,11,12] giving 1 is the case where nothing is in range at all — no swaps happen and the very first index already disagrees.

Follow-ups you should expect: “Why is the answer at most n + 1?” — the pigeonhole argument above; this is the insight the problem is testing. “Prove the while loop is amortised $O(n)$” — each swap fixes one position permanently. “With $O(n)$ space allowed?” — a set of the values, then scan upward from 1; much easier, so say it first. “Restore the original order?” — not possible once swapped; copy first if the caller needs it.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

4 problems

2 easy1 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○268Missing NumbereasyValues `0..n` with one gap -- place each value at its index, or just XOR/sum the differenceNeetCode 150Blind 75
• ○448Find All Numbers Disappeared in an ArrayeasyMark seen values by negating `nums[abs(v) - 1]`; the still-positive slots are the answers
• ○287Find the Duplicate NumbermediumValues `1..n` with one repeat, and the array is read-only -- so use Floyd's cycle detection on the index graphNeetCode 150
• ○41First Missing PositivehardThe hardest of the family: place every value `1..n` at its home index, then scan for the first slot that disagrees

Dry run

nums = [3, 1, 5, 4, 2]. Note that i advances only when a value is already home — that asymmetry is the whole loop.

Step	array	i	nums[i]	home	action
1	[3,1,5,4,2]	0	3	2	swap 0↔2, i stays
2	[5,1,3,4,2]	0	5	4	swap 0↔4, i stays
3	[2,1,3,4,5]	0	2	1	swap 0↔1, i stays
4	[1,2,3,4,5]	0	1	0	already home, i++
5	[1,2,3,4,5]	1	2	1	already home, i++
6–8	unchanged	2,3,4	—	—	already home, i++ each

Three swaps and eight iterations for five elements. The bound is not obvious from the code, so state it explicitly: every swap places at least one value in its permanent home, and a value never leaves home once placed. So there are at most n swaps and at most 2n iterations total — $O(n)$, despite a while loop whose index sometimes fails to advance.

Compare values, not indices, in the swap test

The condition is nums[i] != nums[home], not i != home. With a duplicate value the two slots already hold the same number, so i != home stays true forever and the loop spins. This is the difference between a working solution and an infinite loop, and it is the reason LC 442 and LC 287 are the interesting members of this family.

The variant map

Place everything home, then read the answer off the positions that are wrong.

Variant	After sorting, look for	Canonical problem
Missing number	the first index where nums[i] != i + 1	268 Missing Number · 41 First Missing Positive
Duplicate number	the value sitting where another belongs	287 Find the Duplicate Number
All duplicates	every index where nums[i] != i + 1	442 Find All Duplicates
All missing	same scan, report i + 1 instead of nums[i]	448 Find All Numbers Disappeared
Set mismatch	one missing and one duplicated	645 Set Mismatch

LC 41 is the hard one, and the reason is the range

First Missing Positive allows arbitrary integers, including negatives and values beyond n. The fix is to ignore anything outside 1..n entirely — those values can never be the answer, since with n slots the first missing positive is at most n + 1. Once you say that out loud the problem collapses back to plain cyclic sort.

Pitfalls

• Advancing i after a swap. The value swapped into position i has not been examined yet. Advancing skips it, and the array ends up unsorted.
• Testing i != home instead of nums[i] != nums[home]. Infinite loop on any duplicate. This is the single most common failure here.
• Off-by-one between value and index. Value v belongs at v - 1 for a 1..n range, and at v for a 0..n-1 range. Read the problem statement carefully — both conventions appear.
• Using it without the range promise. No 1..n guarantee means no home index, and the pattern does not apply at all.
• Forgetting to filter out-of-range values in LC 41. Negatives and values above n will index out of bounds or corrupt a slot that mattered.

Interview follow-ups

They ask	What they’re checking	The answer
“Why is this $O(n)$ when i sometimes does not advance?”	Amortised reasoning	Each swap puts at least one value permanently home, so there are at most $n$ swaps and $2n$ iterations in total
“Why not use a hash set?”	Whether you noticed the space constraint	A set is $O(n)$ time but $O(n)$ space. Cyclic sort is $O(1)$ space, which is usually the whole point of the question
“Could you use XOR instead?”	Breadth	For exactly one missing number, yes — XOR of 1..n against the array. It does not generalise to several missing or duplicated values, and it destroys nothing, which cyclic sort does
“What if the input is read-only?”	Whether you know the constraint matters	Cyclic sort mutates, so it is out. Use binary search on the value range (LC 287’s $O(n \log n)$ solution) or Floyd’s cycle detection treating the array as a linked list
“Values are 0..n-1 now”	Attention	Home becomes index v rather than v - 1. Everything else is identical

Self-check

pch.quizTag Cyclic sort — self-check

1. Why does `i` not advance after a swap?

   A It does advance — the swap and the increment happen together B Because the value swapped INTO position i has not been examined yet C To make the loop terminate D It is an optimisation and either works
   pch.quizShowAnswer

   B — Because the value swapped INTO position i has not been examined yet — A swap brings an unexamined value into slot i. Advancing skips it and the array ends up unsorted. Only when nums[i] is already home is it safe to move on.

2. The swap test is `nums[i] != nums[home]` rather than `i != home`. What breaks with the latter?

   A Nothing — they are equivalent B With a duplicate value the two slots already hold the same number, so i != home stays true forever and the loop spins C It causes an index error D It makes the algorithm O(n squared)
   pch.quizShowAnswer

   B — With a duplicate value the two slots already hold the same number, so i != home stays true forever and the loop spins — Compare values, not positions. This is the difference between a working solution and an infinite loop, and it is exactly what LC 442 and LC 287 test.

3. What makes cyclic sort applicable at all?

   A The array being nearly sorted B The values being a permutation of 1..n, so every value has exactly one correct home index C The array being small D The values being distinct
   pch.quizShowAnswer

   B — The values being a permutation of 1..n, so every value has exactly one correct home index — The range promise turns the array into its own lookup table: value v belongs at index v-1, so no comparisons are needed. Without it there is no home to send a value to and the pattern does not apply.

4. LC 41 First Missing Positive allows arbitrary integers. How does that change things?

   A It makes cyclic sort inapplicable B Ignore any value outside 1..n — with n slots the answer is at most n+1, so those values can never be it C Sort the array first D Use a hash set instead
   pch.quizShowAnswer

   B — Ignore any value outside 1..n — with n slots the answer is at most n+1, so those values can never be it — Once you observe the answer is bounded by n+1, everything outside 1..n is irrelevant and the problem reduces to plain cyclic sort. Saying that bound out loud is most of the solution.

5. The array is read-only. What now?

   A Copy it and run cyclic sort B Cyclic sort is out since it mutates — use binary search on the value range, or Floyd cycle detection treating the array as a linked list C Use XOR D It is impossible
   pch.quizShowAnswer

   B — Cyclic sort is out since it mutates — use binary search on the value range, or Floyd cycle detection treating the array as a linked list — Copying costs the O(1) space that was the point. LC 287 explicitly forbids mutation, and its two intended solutions are binary search on the count of values below mid, or Floyd cycle detection.

Recall card

• Cue — values are a permutation of 1..n (or 0..n-1), and the problem demands $O(n)$ time with $O(1)$ space.
• Invariant — value v belongs at index v - 1. Everything left of i is already home.
• Template — while i < n: compute home = nums[i] - 1; if nums[i] != nums[home] swap and do not advance i; else i += 1.
• Complexity — $O(n)$ time (at most n swaps, 2n iterations), $O(1)$ space.
• Remember — compare values in the swap test, never indices; do not advance i after a swap; filter out-of-range values for LC 41.
• Then read the answer off the indices where nums[i] != i + 1.

Recap

• Cyclic sort places every value at its “home” index (value - 1 for a 1..n range) in a single pass — $O(n)$ time, $O(1)$ extra space.
• A swap that fails to change anything is the tell for a duplicate; a final scan for nums[i] != i (or i + 1) reveals what’s missing.
• It only applies when the array’s values are known to fall in a tight range tied to its length — that’s the cue to look for.
• Cue: “numbers from 1 to n” (or 0 to n), “find missing/duplicate,” “in-place, O(1) extra space.”

Together, two pointers, sliding window, fast/slow pointers, merge intervals, and cyclic sort cover a large share of the easy and medium array, string, and linked-list problems you’ll see in a technical interview — practice spotting the cue, and the right pattern (and its $O(n)$ solution) should come to mind quickly.

Next: In-place Linked List Reversal — the prev/curr/next pointer template extended to sublists and groups of k nodes.