Cyclic Sort Pattern

Why this pattern matters for LeetCode

Finding a missing number in an array of 1 to N typically uses a Set (O(n) space) or a sort (O(n log n) time). Cyclic Sort does it in O(n) time and O(1) space. The key insight: if the input contains numbers 1 to N, then number k belongs at index k-1. Walk the array; whenever nums[i] isn't at its correct index, swap it there. After one pass, every correctly placed number is in the right spot and every wrong spot reveals a missing or duplicate number.

What the Cyclic Sort pattern is

Cyclic Sort places each number at its correct index in one pass. For an array containing numbers 1 to N, number k belongs at index k-1. While walking through the array: if nums[i] is not at index nums[i]-1, swap it to its correct position and stay at index i (the swapped-in number may also need placing). If nums[i] is already correct (or is a duplicate already placed), advance to i+1. After the sort, scan for the index where nums[i] !== i+1 — that reveals the missing or duplicate number.

Reach for Cyclic Sort when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Cyclic Sort

• ✓Missing Number — find the one value from 0 to N not in the array
• ✓Find All Missing Numbers — find all values from 1 to N absent from the array
• ✓Find the Duplicate Number — find which value appears twice
• ✓Find All Duplicates — find every value that appears exactly twice
• ✓First Missing Positive — first missing integer > 0 in an unsorted array

When NOT to use Cyclic Sort

• ✕The array values are not in a bounded range — cyclic sort requires knowing where each number 'belongs'
• ✕The range is 0 to N-1 instead of 1 to N — adjust: num k belongs at index k, not k-1
• ✕You need the output in a specific order beyond placing numbers at their indices
• ✕The problem allows duplicate values with no single 'correct index' per value

Better alternative: For unbounded ranges use a hash set (O(n) space). For known-range problems, cyclic sort gives the O(1) space solution.

JavaScript code template

Find the Missing Number — O(n) time, O(1) space

function missingNumber(nums) {
  let i = 0;

  // Cyclic sort: put nums[i] at index nums[i] (range is 0 to N)
  while (i < nums.length) {
    const correct = nums[i]; // nums[i] should live at index nums[i]
    if (correct < nums.length && nums[correct] !== correct) {
      // swap nums[i] and nums[correct]
      [nums[i], nums[correct]] = [nums[correct], nums[i]];
    } else {
      i++;
    }
  }

  // Find the index where nums[i] !== i — that's the missing number
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i) return i;
  }

  return nums.length; // N itself is missing
}

The while loop places each number at its correct index by swapping. The key: only advance i when nums[i] is already correct (or is nums.length, which has no slot). After the sort, a linear scan finds the first index where nums[i] !== i. That index is the missing number. The swap-without-advancing means each number is placed in at most one swap — O(n) total swaps.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Determine where each number 'belongs': for range 1 to N, number k belongs at index k-1. For range 0 to N, number k belongs at index k.
2. 2Walk the array with index i. While nums[i] is not at its correct position (and isn't out of bounds / a duplicate), swap nums[i] to its correct index.
3. 3Do NOT increment i after a swap — the number that landed at i may also need to be placed somewhere.
4. 4Increment i only when nums[i] is already in its correct position.
5. 5After the loop, scan again: the first index where nums[i] doesn't equal the expected value is the answer.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

Coming soon

• Missing Number

  Sort the 0-to-N range in place, then find the first index where nums[i] !== i.

  Coming soon
• Find All Numbers Disappeared in an Array

  After cyclic sort, every index where nums[i] !== i+1 holds a number that displaced the missing one.

  Coming soon
• Find the Duplicate Number

  After cyclic sort, the index where a swap would create a duplicate is the duplicate's correct index.

  Coming soon
• First Missing Positive

  Apply cyclic sort to the positive 1-to-N range, ignoring negatives and values outside range, then find the gap.

  Coming soon

Common mistakes beginners make

• ✕Incrementing i after every step — you'll skip over misplaced numbers that just got swapped in. Only advance when nums[i] is already correct.
• ✕Infinite swap loop — this happens when nums[i] equals the value already at the target index (a duplicate). Check for this before swapping and increment i instead.
• ✕Off-by-one for 1-to-N vs 0-to-N — range 1 to N: num k goes at index k-1. Range 0 to N: num k goes at index k. Mixing these up causes wrong placement.
• ✕Modifying the array when the problem says not to — cyclic sort sorts in place. If the problem forbids mutation, use a hash set instead.

Cyclic Sort vs Hash Set for Missing Numbers

Choose the right tool for the job.

Time and space complexity

Each number is swapped at most once — once it's at its correct index, it's never moved again. The while loop runs at most 2n iterations total (each of n elements is swapped at most once, then advanced past once). The final linear scan is O(n). Total: O(n) time, O(1) extra space (swaps happen in place).

Frequently asked questions

Why doesn't incrementing i after every iteration work?

After a swap, the number that landed at index i is new — it might not be in its correct position either. If you advance i immediately, you'll never sort that new value. You must re-check index i after every swap until the value there is already correct.

How do I handle duplicates during the sort?

Before swapping nums[i] to its target index, check if nums[i] already equals nums[target]. If yes, you'd be swapping identical values and looping forever. When they're equal, advance i instead of swapping — that number is a duplicate and the slot is already occupied.

Can cyclic sort handle arrays with values outside the 1-to-N range?

For values outside the range (like negative numbers or values > N), just skip them — increment i without swapping. They have no correct position in the 1-to-N scheme. First Missing Positive uses this: ignore values ≤ 0 and > N, cyclically sort the rest.

Why is the time complexity O(n) even though there's a while loop inside the outer loop?

Each element is swapped at most once — once a number reaches its correct index, it's never moved again. The total number of swaps across all iterations of the outer loop is at most n. So the combined total of all inner-loop iterations is bounded by n. O(n) total.