Cyclic Sort

TL;DR

When the input is n integers drawn from 1..n (or 0..n-1), cyclic sort sorts in place in O(n) time and O(1) extra space. Walk once. For each cell, swap whatever’s there into the slot its value names. Repeat until the cell is correct, then advance. No comparisons against neighbours, no merge buffer, no counting array.

The pattern earns its name from the second-order payoff. Once nums[i] == i + 1 is the definition of sorted, any index where the invariant breaks tells you exactly which value is missing, duplicated, or out of range. A whole class of problems — first missing positive (LC 41), missing number (LC 268), find all duplicates (LC 442) — collapses to “cyclic-sort, then one linear scan.”

The picture in your head

It’s a wedding with assigned seating. Each guest is holding a card with their seat number. You walk in at chair 0 and ask whoever’s sitting there for their card. They say “seat 4.” You and that guest swap: they go to chair 4, the person previously at chair 4 is now at chair 0. You ask the new occupant of chair 0 for their card. Repeat until the person at chair 0 is the one assigned to chair 0. Then move to chair 1.

Each swap puts at least one guest in their permanent seat. Once seated correctly, they never move again. With n guests, the whole hall is seated in at most n swaps — even though chair 0 alone might take several swaps before its rightful occupant arrives.

The problem it solves

The textbook fix for “sort this array” is nums.sort(): O(n log n) time, O(1) extra space if the sort is in-place. That’s optimal for general inputs, because comparison sorting has an Ω(n log n) lower bound.

But comparison sorting is general because it has to handle anything. When the input is a permutation of 1..n, you already know what the sorted array looks like — it’s [1, 2, ..., n]. There’s nothing to discover, only to rearrange. Each value v has a known home (v - 1), so the sort degenerates into “send each value home.” That’s a linear job.

The savings compound when the question isn’t “sort it” but “what’s missing?” or “what’s duplicated?” A hash set answers both in O(n) time but pays O(n) memory. Cyclic sort matches the time and keeps the memory at O(1) — the only linear-time, constant-space option in the toolbox.

When to reach for it

Strong signals:

• The problem states (or implies) the array is a permutation of 1..n — or 0..n-1, or “n integers in the range [1, n]”. This is the hard signal; without it the pattern doesn’t apply.
• You need a missing number, duplicate, or first missing positive in O(n) time and O(1) space. The space bound kills the hash-set solution and points straight here.
• You’re allowed to mutate the input. Cyclic sort is destructive.

Signals it’s not cyclic sort: values aren’t bounded by n, the array contains arbitrary integers with no clean range, the input is read-only, or duplicate ordering must be preserved (use counting sort or a hash map).

Flavor 1 — basic cyclic sort

The canonical template, for an array containing 1..n with no duplicates.

def cyclic_sort(nums: list[int]) -> None:
    i = 0
    while i < len(nums):
        correct = nums[i] - 1   # value v belongs at index v - 1
        if nums[i] != nums[correct]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1

Note the else: i += 1. We only advance i when the current cell is already correct (or holds a value equal to the one already at its home — relevant once duplicates show up). Otherwise we swap and re-examine the same i, because the new nums[i] might also be out of place.

Worked example. nums = [3, 1, 5, 4, 2], n = 5.

Three swaps, then four cheap i++ checks. Eight loop iterations on a five-element array — linear, as advertised.

Flavor 2 — find the missing number (LC 268)

Array of length n containing n distinct values from 0..n — exactly one is missing. Same skeleton, but the home of value v is now index v (not v - 1), and we must guard against nums[i] == n (no slot for it).

def missing_number(nums: list[int]) -> int:
    i, n = 0, len(nums)
    while i < n:
        correct = nums[i]
        if nums[i] < n and nums[i] != nums[correct]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i:
            return i
    return n

Worked example. nums = [4, 0, 3, 1], n = 4. The missing value is 2.

Final scan: nums[0]=0, nums[1]=1, nums[2]=4 ≠ 2 — return 2.

Flavor 3 — duplicates and first missing positive (LC 41)

Given an unsorted array of arbitrary integers, return the smallest missing positive integer in O(n) time, O(1) space. The answer must lie in [1, n + 1], so any value outside [1, n] is irrelevant — we just leave those cells alone.

def first_missing_positive(nums: list[int]) -> int:
    i, n = 0, len(nums)
    while i < n:
        correct = nums[i] - 1
        if 1 <= nums[i] <= n and nums[i] != nums[correct]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

The 1 <= nums[i] <= n guard is what distinguishes this flavor — it both filters garbage (zeros, negatives, values larger than n) and prevents out-of-bounds writes. The nums[i] != nums[correct] clause stops us swapping two equal values forever (the duplicate case).

Worked example. nums = [3, 4, -1, 1], n = 4.

Final scan: index 1 holds -1, not 2 — return 2.

The same skeleton solves find all duplicates (LC 442) — after sorting, any index where nums[i] != i + 1 holds a value that appears twice — and find all numbers disappeared (LC 448) — the indices themselves are the missing values. One template, three problems.

Why it works — the invariant

Each iteration of the loop either advances i (cell is correct) or performs a swap that places at least one value into its permanent home — the slot dictated by its value. Once a value is home, it never moves again, because the swap condition nums[i] != nums[correct] only fires when the destination cell holds the wrong value.

So across the whole run, every successful swap retires one cell from the “still wrong” set. There are n cells. Therefore at most n swaps. The i pointer also advances at most n times. Total work is bounded by 2n — linear.

Complexity

• Time: O(n) amortized. The naive worry — “the inner loop swaps repeatedly without i moving” — is real but bounded. Each swap costs one unit of work and permanently parks one value, so the global swap count is ≤ n. Add the at-most-n i++ advances and you’re done in 2n operations.
• Space: O(1). Two integers (i, correct) and an in-place swap. The trailing scan that reads off the answer is also O(1) extra.

Common pitfalls

• Off-by-one between 1..n and 0..n-1 indexing. correct = nums[i] - 1 for the 1..n family; correct = nums[i] for the 0..n-1 family. Mixing them silently corrupts the array. Pick the convention before you start writing and stick to it.
• Infinite loop on duplicates. If you write if nums[i] != correct + 1 instead of if nums[i] != nums[correct], two equal values will swap each other forever. Always compare to the value at the destination, not to the index.
• Applying it to arrays not in [1, n] range. If the input can hold arbitrary integers, you must add a range guard (1 <= nums[i] <= n) before computing correct, or you’ll index out of bounds.
• Using i += 1 inside the swap branch. The whole point of the pattern is that after a swap, the new nums[i] is also probably out of place, so you re-examine the same index. Advancing i after every swap turns O(n) into a buggy partial sort that misses elements.
• Forgetting the post-loop scan. Cyclic sort is the setup; the answer to missing/duplicate problems comes from the linear pass that follows. New writers often return mid-loop and miss obvious cases.

Where you see this in production

• NumPy permutation tests. np.testing.assert_array_equal against a reference permutation, and the internals of np.argsort checks for contiguous index ranges, lean on the same “value v lives at slot v” invariant — it’s the cheapest way to validate a permutation in place.
• Spark range partitioner. Spark’s RangePartitioner samples keys to build bucket boundaries, then routes records to in-memory slot arrays whose indices are derived from the key’s rank. Compacting those slots before a shuffle write is a cyclic-sort-style in-place rearrange.
• Database vacuum / ID compaction. PostgreSQL’s VACUUM FULL and similar compaction passes in OLAP engines (DuckDB, ClickHouse) rewrite row IDs into a contiguous 0..n-1 range. The relabel step is the fixed-domain analogue of cyclic sort — every row goes to the slot its new ID names.
• Slot-based memory allocators. Slab and arena allocators (Linux’s SLUB, jemalloc’s bin arrays) maintain free lists indexed by slot number; reclamation passes that consolidate freed slots into contiguous runs use the same “send each item to the slot named by its ID” movement pattern.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.