Pattern 5: Cyclic Sort

Deep Dive: Place Each Number at Its Home

Find Missing Number in [1, n]

nums = [3, 1, 4, 2, 6] (n=6, one number missing):

Sort in-place by swapping each to correct index:
  i=0: nums[0]=3, should be at index 2. Swap: [4,1,3,2,6]
  i=0: nums[0]=4, should be at index 3. Swap: [2,1,3,4,6]
  i=0: nums[0]=2, should be at index 1. Swap: [1,2,3,4,6]
  i=0: nums[0]=1, correct! Move on.
  i=1..4: all correct.

Result: [1,2,3,4,6]
         0 1 2 3 4  <- index 4 has value 6, not 5. MISSING = 5.

Key: After cyclic sort, scan for the first index where nums[i] != i+1. That index reveals the missing number.

---

Signal: Array contains numbers in range [1, n] or [0, n], find missing/duplicate Template: Place each number at its correct index: nums[i] should be at nums[nums[i]-1]

When to Use

• "Find the missing number" in [1, n]
• "Find the duplicate number" in [1, n]
• "Find all missing numbers"
• Array of size n with values in [1, n]

Key Idea

While nums[i] != nums[nums[i]-1]: swap nums[i] to its correct position.
After sorting, any i where nums[i] != i+1 is missing/duplicate.

Re-solve (TIMED)

Problem	Target Time	Done?
Missing Number (LeetCode #268)	10 min	[ ]

New Practice Problems

Add problems to solutions/ and enrich as needed.

---

First-time Recognition Signals

When you read a brand-new problem statement, this pattern is the right tool if you see:

• "Array of size n with values in the range [1, n] (or [0, n−1])" combined with a missing / duplicate / first-k-missing question — values double as indices, so each element has a "home".
• "Find all numbers disappeared / find the duplicate" with the constraint "O(n) time and O(1) extra space" — the O(1) space tag almost always rules out HashSet and points at cyclic sort.
• "First missing positive" — the canonical hard cyclic-sort problem; ignore values outside [1, n] and place the rest.
• "Find the corrupt pair (one number missing, one duplicated)" — place each number at its home, then scan for the mismatch.

Anti-signals (looks like this pattern, isn't)

• "Find the missing number in an unsorted array of arbitrary integers" — no [1, n] guarantee, so values cannot index into the array; use XOR, sum formula, or HashSet.
• "Sort an array of arbitrary integers" — quicksort/mergesort. Cyclic sort only works because of the special value range.
• "Find the duplicate number" when extra space is allowed — HashSet is simpler and clearer; reach for cyclic sort only when O(1) space is required.