Cyclic Sort

Whenever a problem hands you an array containing numbers from a known range — typically 1..n1..n or 0..n-10..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..n1..n exactly once, number vv would belong at index v - 1v - 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 whilewhile inside the forfor.
Worked example: finding the missing number in a 0..n0..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 pattern

Walk the array with index ii. While the value at ii 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]

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 ii 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 nn 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

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 nn distinct numbers from 00 to nn with exactly one missing, cyclic sort each value to index valuevalue (adjusting for the 0..n0..n range instead of 1..n1..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

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..n1..n in an array of size n + 1n + 1 guarantee at least one duplicate. Cyclic-sort each value toward index value - 1value - 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_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

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..n1..n (or 0..n0..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 nn distinct numbers drawn from [0, n][0, n], return the one number that is missing.

Constraints. n == len(nums)n == len(nums), 1 <= n <= 10^41 <= 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][3,0,1] gives 22 · [0,1][0,1] gives 22 · [9,6,4,2,3,5,7,0,1][9,6,4,2,3,5,7,0,1] gives 88

Editorial — approach, complexity, follow-ups

The values are a permutation of [0, n][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)len(nums) matters: indices run 0..n-10..n-1 but values run 0..n0..n, so the index nn must be contributed manually.

[0][0] giving 11 and [1][1] giving 00 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)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 nn. 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..n1..n instead of 0..n0..n?” — shift the pairing by one. “Find the duplicate instead (LC 287)?” — values 1..n1..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 nn integers where each value is in [1, n][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^51 <= n <= 10^5, 1 <= nums[i] <= n1 <= nums[i] <= n.

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

Editorial — approach, complexity, follow-ups

Because every value lies in [1, n][1, n], value vv has a natural home at index v - 1v - 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)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] > 0if 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][1,1] is the minimal test: without the guard, index 0 is negated twice and 11 is wrongly reported missing.

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

If mutating the input is unacceptable, a setset 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 absabs 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^51 <= len(nums) <= 10^5, -2^31 <= nums[i] <= 2^31 - 1-2^31 <= nums[i] <= 2^31 - 1.

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

Editorial — approach, complexity, follow-ups

The key observation is a bound on the answer: with nn slots, the values 1..n1..n either all appear — making the answer n + 1n + 1 — or one of them is missing. So nothing outside 1..n1..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 - 1value - 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 nn swaps — the whilewhile does not make it quadratic. Space $O(1)$ .

Three details, each with a test case:

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

[7,8,9,11,12][7,8,9,11,12] giving 11 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 + 1n + 1?” — the pigeonhole argument above; this is the insight the problem is testing. “Prove the whilewhile loop is amortised $O(n)$ ” — each swap fixes one position permanently. “With $O(n)$ space allowed?” — a setset 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

#	Problem	Difficulty	The twist
268	Missing Number	Easy	Values `0..n0..n` with one gap — place each value at its index, or just XOR/sum the difference
448	Find All Numbers Disappeared in an Array	Easy	Mark seen values by negating `nums[abs(v) - 1]nums[abs(v) - 1]`; the still-positive slots are the answers
287	Find the Duplicate Number	Medium	Values `1..n1..n` with one repeat, and the array is read-only — so use Floyd’s cycle detection on the index graph
41	First Missing Positive	Hard	The hardest of the family: place every value `1..n1..n` at its home index, then scan for the first slot that disagrees

Recap

Cyclic sort places every value at its “home” index (value - 1value - 1 for a 1..n1..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] != inums[i] != i (or i + 1i + 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 kk nodes.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Cyclic Sort

What you’ll learn

The pattern

How it works

Worked example

Time and space complexity

When to use it

Practice — real LeetCode problems

LC 268 — Missing Number · Easy

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

LC 41 — First Missing Positive · Hard

LeetCode problem set

Recap

Was this page helpful?