Cyclic Sort and First Missing Positive: O(n) Time, O(1) Space

"Find the smallest missing positive integer in linear time and constant extra space" reads like a trick question. A hash set gives linear time but not constant space; sorting gives constant space but not linear time. The way out is a pattern with a plain name: cyclic sort. It works whenever the values tell you where they belong, and it turns the array into its own lookup table.

The problem it solves

A family of questions shares one shape: an array of length n whose values are supposed to be the numbers 1 to n, except some are missing, repeated or out of range.

• Find the missing number, or all missing numbers.
• Find the duplicates.
• Find the first missing positive, where the input can hold anything: zeros, negatives, huge values.

A hash set solves all of them in O(n) time with O(n) extra memory. Cyclic sort solves them in O(n) time with O(1) extra memory, by rearranging the input in place.

The intuition

If the values are 1 to n, value v has an obvious home: index v - 1. So walk the array with a cursor. Look at the value under it. If it is not home, swap it straight home — and do not move the cursor, because the swap just brought a new, unexamined value under it. If the value is home, or its home is already occupied by an equal value, move on.

Why is that linear, when the loop sometimes stays put? Because every swap places one value in its final slot, and a placed value is never moved again. There can be at most n swaps and at most n cursor steps, so at most 2n iterations.

After the pass, any slot i that does not hold i + 1 tells you two things at once: i + 1 is missing, and the value sitting there is a duplicate or an outsider.

For first missing positive, add one rule: values outside 1..n have no home, so leave them where they are. They get overwritten by swaps or left behind in slots that become the answer.

Watch it run

The animation sorts the lesson's array [3, 1, 5, 4, 2]. The cursor stays at index 0 while three swaps happen there: 3 goes to index 2, then 5 to index 4, then 2 to index 1, and the 1 that comes back belongs at index 0. From then on every slot is already settled and the cursor only walks. Three swaps, five values placed, no comparisons between neighbours.

The code

The basic sort, and the missing-and-duplicates variant built on it. The nums[i] != nums[home] test is what makes duplicates safe: if the home already holds the same value, swapping would loop forever.

def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        home = nums[i] - 1                      # value v belongs at index v - 1
        if nums[i] != nums[home]:
            nums[i], nums[home] = nums[home], nums[i]
        else:
            i += 1                              # settled (or a duplicate): move on
    return nums

print(cyclic_sort([3, 1, 5, 4, 2]))             # [1, 2, 3, 4, 5]

def missing_and_duplicates(nums):               # values in 1..n, some repeated
    cyclic_sort(nums)
    missing = [i + 1 for i, v in enumerate(nums) if v != i + 1]
    dupes = sorted({v for i, v in enumerate(nums) if v != i + 1})
    return missing, dupes

print(missing_and_duplicates([4, 3, 2, 7, 8, 2, 3, 1]))   # ([5, 6], [2, 3])

First missing positive. The only change is the range check before swapping; the answer is the first slot that does not hold its own value, or n + 1 if every slot does:

def first_missing_positive(nums):
    n = len(nums)
    i = 0
    while i < n:
        v = nums[i]
        if 1 <= v <= n and nums[v - 1] != v:    # in range and not home yet
            nums[i], nums[v - 1] = nums[v - 1], nums[i]
        else:
            i += 1                              # out of range, duplicate, or home
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1                        # first slot without its own value
    return n + 1                                # 1..n are all present

print(first_missing_positive([3, 4, -1, 1]))    # 2
print(first_missing_positive([7, 8, 9]))        # 1
print(first_missing_positive([1, 2, 3]))        # 4

Why is the answer never larger than n + 1? An array of n values can contain at most n distinct positives, so at least one of 1, 2, …, n + 1 is absent.

The check below compares each function with the most literal reference possible — count upward from 1 until a number is not in the list, and scan for missing values and repeats directly — on 5,000 random arrays that include negatives, zeros, repeats and values larger than n:

import random

random.seed(7)
ok = True
for _ in range(5000):
    n = random.randint(0, 12)
    nums = [random.randint(-3, n + 3) for _ in range(n)]
    want = 1
    while want in nums:                         # brute force: count up from 1
        want += 1
    ok &= first_missing_positive(nums[:]) == want

    perm = random.sample(range(1, n + 1), n)    # a permutation of 1..n
    ok &= cyclic_sort(perm[:]) == sorted(perm)

    vals = [random.randint(1, n) for _ in range(n)] if n else []
    miss, dup = missing_and_duplicates(vals[:])
    ok &= miss == [v for v in range(1, n + 1) if v not in vals]
    ok &= dup == sorted(v for v in set(vals) if vals.count(v) > 1)
print(ok)                                       # True

The complexity

O(n) time: at most n swaps, because each one parks a value permanently, plus at most n cursor steps. O(1) extra space: the array itself is the bookkeeping. The price is that the input is modified. If the caller needs it unchanged, copy it first, and the space advantage over a hash set is gone.

Where it goes wrong

• Swapping when the home holds an equal value. With duplicates, nums[i] != nums[home] is the guard. Comparing indices (i != home) instead loops forever on inputs like [2, 2].
• Moving the cursor after a swap. The value that just arrived has not been examined. Advancing skips it and leaves it out of place.
• Forgetting the range check. In first missing positive, a 0, a negative or a value above n has no home; indexing with it crashes or, in Python, silently wraps to the end of the list.
• Applying it to arbitrary values. Cyclic sort needs values that map onto indices. For general numbers, sort or use a set.

How to say it in an interview

"The values are supposed to be 1 to n, so value v belongs at index v minus 1. I walk the array and keep swapping the current value to its home until the slot holds its own value, an out-of-range value, or a duplicate; then I move on. Every swap places one value for good, so it's O(n) time and O(1) extra space. Afterwards the first index i that doesn't hold i plus 1 gives the first missing positive, and if all slots match, the answer is n plus 1."

A close relative uses no swaps at all: XOR tricks find a single missing number in one pass. For partitioning an array in place by value instead of by index, see the Dutch national flag.