Cyclic Sort

Find Missing Number

Place each number at its correct index. After cyclic placement, scan the array — the index where nums[i] ≠ i+1 tells you which number is missing. O(n) time, O(1) space.

O(n)

O(1)

How It Works

Cyclic sort exploits arrays whose values are a permutation-like range such as [0, n] or [1, n]: each value has exactly one home index (value v belongs at index v or v−1). Sweep the array; whenever the current element is not at its home and its home holds a different value, swap it home. Each swap places at least one element permanently, so despite the nested-looking logic the total swaps are bounded by n.

After this O(n) rearrangement, a second scan finds the index whose occupant is wrong — that index names the missing number. The approach matches the O(n) time of the sum-formula or XOR tricks while generalizing to variants those tricks cannot handle, all with O(1) extra space.

Step-by-Step Visualization

Cyclic sort: place each number at index num-1

Goalnums[i] = i+1

1/3

Code

Java

static int findMissing(int[] nums) {
  int i = 0;
  while (i < nums.length) {
    int correct = nums[i] - 1;
    if (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[correct]) {
      int tmp = nums[i]; nums[i] = nums[correct]; nums[correct] = tmp;
    } else i++;
  }

  for (int j = 0; j < nums.length; j++)
    if (nums[j] != j + 1) return j + 1;
  return nums.length + 1;
}

Tips & Gotchas

1Place each number at its correct index: nums[i] should be i+1

2Swap nums[i] with nums[nums[i]-1] until positioned correctly

3After sorting, the first index where nums[i] !== i+1 is the missing number

Practice Problems

1Missing Number
2First Missing Positive
3Set Mismatch
4Kth Missing Positive Number

About the Cyclic Sort Pattern

When an array contains numbers in the range [1, n] (or [0, n]), you can place each number at its 'correct' index (number i goes to index i−1). After sorting, any index without its correct number reveals the missing or duplicate value.

Key insight

When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.

Common Array Interview Problems

Two Sum
Best Time to Buy & Sell Stock
Maximum Subarray
Merge Intervals
Product of Array Except Self
Container With Most Water

Frequently Asked Questions

Why use cyclic sort when Gauss's sum formula also finds the missing number?

For a single missing value the sum or XOR trick is shorter, but it collapses the array into one scalar and cannot say more. Cyclic sort restores full positional structure, so the same code extends to multiple missing numbers, duplicates, and first-missing-positive, and the sum trick risks overflow in fixed-width languages.

How is cyclic sort O(n) when there is a while-loop inside the for-loop?

Every swap moves some element into its final home, and once home an element never moves again. At most n such placements can occur across the whole run, so the inner while-loop's total iterations are bounded by n regardless of how they cluster.