Cyclic Sort Pattern — Missing and Duplicate Numbers in O(1) Space

Q: When should I use cyclic sort?

When the array contains n numbers from a known contiguous range — usually 1..n or 0..n — and the question asks which are missing, duplicated, or out of place. That range guarantee is what lets each value have a home index, which is what makes O(1) space possible.

Q: Why is cyclic sort O(n) when it has a while loop with swaps inside?

Every swap places at least one value permanently into its correct slot, and a value never leaves once home. So the total number of swaps across the whole run is bounded by n, and the cursor advances n times — O(n) overall despite the nested-looking structure.

Q: How does First Missing Positive avoid extra space?

The answer must lie in 1..n+1, because n slots cannot contain all of 1..n and still miss something smaller. So values outside that range are ignored, the rest are cyclically sorted in place, and the answer is the first index not holding its own value — or n+1 if every index does.

A narrow pattern with an unmistakable trigger: the array holds n numbers drawn from 1..n (or 0..n). That constraint is not flavour text — it means every value has a natural home index, so the array can act as its own hash map and the O(n) extra space the obvious solution needs disappears.

The idea

Value v belongs at index v - 1 (or at index v for 0-based ranges). Walk the array; whenever the value under your cursor is not home, swap it to where it belongs. Do not advance until the current slot holds the right value or the swap would be a no-op.

def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        home = nums[i] - 1                    # 1..n → index 0..n-1
        if 0 <= home < len(nums) and nums[i] != nums[home]:
            nums[i], nums[home] = nums[home], nums[i]
        else:
            i += 1                            # in place, or a duplicate — move on
    return nums

void cyclicSort(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        int home = nums[i] - 1;               // 1..n → index 0..n-1
        if (home >= 0 && home < nums.length && nums[i] != nums[home]) {
            int tmp = nums[i];                // compare VALUES, not indices,
            nums[i] = nums[home];             // or duplicates loop forever
            nums[home] = tmp;
        } else {
            i++;
        }
    }
}

void cyclicSort(vector<int>& nums) {
    int i = 0;
    while (i < (int)nums.size()) {
        int home = nums[i] - 1;               // 1..n → index 0..n-1
        if (home >= 0 && home < (int)nums.size() && nums[i] != nums[home]) {
            swap(nums[i], nums[home]);        // compare VALUES, not indices
        } else {
            i++;
        }
    }
}

void cyclicSort(int* nums, int n) {
    int i = 0;
    while (i < n) {
        int home = nums[i] - 1;               /* 1..n → index 0..n-1 */
        if (home >= 0 && home < n && nums[i] != nums[home]) {
            int tmp = nums[i];                /* compare VALUES, not indices */
            nums[i] = nums[home];
            nums[home] = tmp;
        } else {
            i++;
        }
    }
}

function cyclicSort(nums) {
  let i = 0;
  while (i < nums.length) {
    const home = nums[i] - 1;                 // 1..n → index 0..n-1
    if (home >= 0 && home < nums.length && nums[i] !== nums[home]) {
      [nums[i], nums[home]] = [nums[home], nums[i]];   // compare VALUES
    } else {
      i++;
    }
  }
  return nums;
}

After sorting, an index holding the wrong value tells you both what is missing (i + 1) and what is duplicated (nums[i]).

Once that loop ends, every index either holds its own value or holds evidence of what is missing. The whole family of questions is one more pass to read that off.

Compare against `nums[home]`, not against `home`. Swapping while nums[i] != home + 1

loops forever on duplicates, because the value has nowhere to go. Comparing values means a duplicate makes the condition false immediately and the cursor advances.

Reading the answer off

def find_disappeared(nums):
    cyclic_sort(nums)
    return [i + 1 for i, v in enumerate(nums) if v != i + 1]

def find_duplicates(nums):
    cyclic_sort(nums)
    return [v for i, v in enumerate(nums) if v != i + 1]

List<Integer> findDisappeared(int[] nums) {
    cyclicSort(nums);
    List<Integer> out = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) out.add(i + 1);      // what is MISSING
    }
    return out;
}

List<Integer> findDuplicates(int[] nums) {
    cyclicSort(nums);
    List<Integer> out = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) out.add(nums[i]);    // what is DOUBLED
    }
    return out;
}

vector<int> findDisappeared(vector<int>& nums) {
    cyclicSort(nums);
    vector<int> out;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (nums[i] != i + 1) out.push_back(i + 1);      // what is MISSING
    }
    return out;
}

vector<int> findDuplicates(vector<int>& nums) {
    cyclicSort(nums);
    vector<int> out;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (nums[i] != i + 1) out.push_back(nums[i]);    // what is DOUBLED
    }
    return out;
}

function findDisappeared(nums) {
  cyclicSort(nums);
  return nums.map((v, i) => (v !== i + 1 ? i + 1 : null))
             .filter(v => v !== null);          // what is MISSING
}

function findDuplicates(nums) {
  cyclicSort(nums);
  return nums.filter((v, i) => v !== i + 1);    // what is DOUBLED
}

Same sort, two different reads: an index whose value is wrong tells you both which number is missing (i + 1) and which number is doubled (nums[i]).

Question	After sorting, the answer is
Missing Number	the first index where `nums[i] != i`
Find All Numbers Disappeared	every `i + 1` where `nums[i] != i + 1`
Find All Duplicates	every `nums[i]` where `nums[i] != i + 1`
First Missing Positive	the first index where `nums[i] != i + 1`

First Missing Positive

The Hard one, and the reason the pattern is worth knowing. It asks for the smallest missing positive integer in O(n) time and O(1) space, on an array with arbitrary values — negatives, zeros, numbers far larger than n.

The insight: the answer is always in 1..n + 1. An array of n slots cannot hide 1 through n and still be missing something smaller. So every value outside that range is irrelevant and can be ignored by the 0 <= home < len(nums) guard already in the loop. Sort what is left cyclically, then return the first index that is not holding its own value — or n + 1 if all of them are.

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

int firstMissingPositive(int[] nums) {
    int n = nums.length, i = 0;
    while (i < n) {
        int home = nums[i] - 1;
        // The bounds check silently ignores negatives and anything > n,
        // which is exactly what we want: the answer lies in 1..n+1.
        if (home >= 0 && home < n && nums[i] != nums[home]) {
            int tmp = nums[i];
            nums[i] = nums[home];
            nums[home] = tmp;
        } else {
            i++;
        }
    }
    for (int j = 0; j < n; j++) {
        if (nums[j] != j + 1) return j + 1;
    }
    return n + 1;
}

int firstMissingPositive(vector<int>& nums) {
    int n = (int)nums.size(), i = 0;
    while (i < n) {
        int home = nums[i] - 1;
        // Bounds check ignores negatives and values > n — the answer is in 1..n+1.
        if (home >= 0 && home < n && nums[i] != nums[home]) {
            swap(nums[i], nums[home]);
        } else {
            i++;
        }
    }
    for (int j = 0; j < n; j++) {
        if (nums[j] != j + 1) return j + 1;
    }
    return n + 1;
}

int firstMissingPositive(int* nums, int n) {
    int i = 0;
    while (i < n) {
        int home = nums[i] - 1;
        /* Bounds check ignores negatives and values > n. */
        if (home >= 0 && home < n && nums[i] != nums[home]) {
            int tmp = nums[i];
            nums[i] = nums[home];
            nums[home] = tmp;
        } else {
            i++;
        }
    }
    for (int j = 0; j < n; j++) {
        if (nums[j] != j + 1) return j + 1;
    }
    return n + 1;
}

function firstMissingPositive(nums) {
  const n = nums.length;
  let i = 0;
  while (i < n) {
    const home = nums[i] - 1;
    // Bounds check ignores negatives and values > n — answer is in 1..n+1.
    if (home >= 0 && home < n && nums[i] !== nums[home]) {
      [nums[i], nums[home]] = [nums[home], nums[i]];
    } else {
      i++;
    }
  }
  for (let j = 0; j < n; j++) {
    if (nums[j] !== j + 1) return j + 1;
  }
  return n + 1;
}

Complexity

O(n) time, O(1) space. The while loop looks like it could be quadratic, but each swap puts at least one value permanently in its home slot, so there are at most n swaps across the whole run — the same amortisation argument as the sliding window.

Mistakes that cost the round

`for` instead of `while`. After a swap the current slot holds a new value that may

itself need moving, so the cursor must not advance automatically.

Comparing indices instead of values, which spins forever on duplicates.
Getting the offset wrong. 1..n maps to nums[v - 1]; 0..n maps to nums[v].

Missing Number is the 0-based one and is the usual place this slips.

Reaching for it without the range guarantee. No 1..n constraint, no cyclic sort —

use a hash set and say why.

What to drill

Missing Number — 0-based, and also solvable by XOR or by Gauss's sum.
Find All Numbers Disappeared in an Array — the standard read.
Find All Duplicates in an Array — the same sort, the other read.
First Missing Positive — the Hard variant with the 1..n + 1 argument.

All on the 22 DSA Patterns sheet.

Frequently asked

When should I use cyclic sort?

When the array contains n numbers from a known contiguous range — usually 1..n or 0..n — and the question asks which are missing, duplicated, or out of place. That range guarantee is what lets each value have a home index, which is what makes O(1) space possible.

Why is cyclic sort O(n) when it has a while loop with swaps inside?

Every swap places at least one value permanently into its correct slot, and a value never leaves once home. So the total number of swaps across the whole run is bounded by n, and the cursor advances n times — O(n) overall despite the nested-looking structure.

How does First Missing Positive avoid extra space?

The answer must lie in 1..n+1, because n slots cannot contain all of 1..n and still miss something smaller. So values outside that range are ignored, the rest are cyclically sorted in place, and the answer is the first index not holding its own value — or n+1 if every index does.

Cyclic Sort (Index-Based)