patternDSA/Cyclic Sort

Core Pattern → Pattern 11

Cyclic Sort

Numbers in range [1..n] belong at a specific index. Swap each to its home in one pass. Then scan for violations — missing or duplicate in O(1) space.

Frequency:★★★☆☆

·~30 min·Beginner–Intermediate·8 problems

Prev In-place Reversal of a Linked List

The Core Shock

Find missing/duplicates with a HashSet — O(n) space. Cyclic Sort — O(1) space

HashSet

O(n) space

n=1M → 1M entries in memory

Sort + Scan

O(n log n)

Modifies array, loses original order

Cyclic Sort

O(n) · O(1)

In-place, single pass, zero extra

The insight: if numbers are in range [1..n], each number has a predetermined home. nums[i] = k belongs at index k-1. Swap it there. After one pass, every number sits at its correct index — or reveals itself as a duplicate by finding its spot already occupied by a copy.

The Key Insight: Value → Index Mapping

One constraint unlocks everything — memorize this mapping.

Range [1..n] — 1-indexed

nums[i] = k → belongs at index k−1
Condition: nums[i] ≠ i+1
Swap to: j = nums[i] − 1

j = nums[i] - 1
if nums[i] != nums[j]:
    swap(i, j)

Examples: Cyclic Sort, Find Missing #, Find All Missing, Duplicate, Corrupt Pair

Range [0..n−1] — 0-indexed

nums[i] = k → belongs at index k
Condition: nums[i] ≠ i
Swap to: j = nums[i]

j = nums[i]
if nums[i] != nums[j]:
    swap(i, j)

Less common variant — same logic, different offset

The duplicate guard: always check nums[i] != nums[j] before swapping — not just nums[i] != i+1. If both positions hold the same value, swapping would cause an infinite loop. Skip and advance i instead.

The 3-Step Framework

Two phases — sort, then scan. Always in that order.

Identify the correct index

For range [1..n]: correct index = nums[i] - 1. For range [0..n-1]: correct index = nums[i]. This is the only formula you need to derive before writing any loop.

# Range [1..n]
correct_idx = nums[i] - 1

# Range [0..n-1]  
correct_idx = nums[i]

Always confirm the range with the problem. [1..n] is most common. If range is [0..n], the formula changes.

Sort phase — swap until all correct

While i < n: if nums[i] is not at correct_idx AND nums[i] != nums[correct_idx] → swap. Otherwise advance i. Do NOT advance i after a swap — recheck the new value at i.

while i < len(nums):
    j = nums[i] - 1
    if nums[i] != nums[j]:  # guard!
        nums[i], nums[j] = nums[j], nums[i]
    else:
        i += 1

The inner while disguises itself as O(n²) but each swap places at least one number correctly — total swaps ≤ n → O(n) amortized.

Scan phase — find violations

After sorting, scan i from 0 to n-1. If nums[i] != i+1: that index is missing i+1, and the value nums[i] is the duplicate. Collect all violations for 'find all' variants.

for i in range(len(nums)):
    if nums[i] != i + 1:
        missing.append(i + 1)    # missing
        duplicate.append(nums[i]) # duplicate

For 'find smallest missing positive': after sort, scan for nums[i] != i+1. First violation = answer. Numbers outside [1..n] stay wherever they land — ignore them.

Pattern Recognition

The one constraint that signals cyclic sort every time.

Use Cyclic Sort When

"Array contains numbers in range [1..n]"

"Find missing number(s)"

"Find duplicate number(s)"

"Find the corrupt pair" (one dup + one missing)

"Find smallest missing positive"

Problem says O(1) extra space required

Array length = n, values 1..n (pigeonhole)

"Find first K missing positives"

Use Other Approaches When

Values not in [1..n] → XOR or sum formula

Array not modifiable → HashSet required

Need original positions preserved → sort separately

Range is very large (e.g., [1..10⁹]) → not applicable

Linked list → Fast & Slow Pointers for cycle

Matrix → DFS/BFS flood fill

Need count of each → HashMap

Sorted already → Binary Search for missing

On this page