Pattern #13 — Cyclic Sort 🔁

Pattern #13 — Cyclic Sort 🔁

This is a little-known but super elegant trick. It only applies to a specific situation, but when it does, it's magic — O(n) time and O(1) space.

1. The Special Situation

   Cyclic Sort works when the array contains numbers in a known
   RANGE, usually 1 to n (or 0 to n-1), possibly shuffled.

   [3, 1, 5, 4, 2]   ← contains exactly 1,2,3,4,5 in some order

   The key insight: each number has a "home" — the value 1
   belongs at index 0, value 2 at index 1, and so on.
   value v → belongs at index v-1.

2. The Idea (in one line)

Walk the array and put each number in its correct "home" index by swapping.

   Real-life analogy 🎟️
   ────────────────────
   Numbered seats 1–5 at a theatre, but everyone sat randomly.
   You go person by person: "You're ticket 3? Go to seat 3."
   You swap them with whoever's wrongly in seat 3. Keep going
   until everyone's in their own seat. Done in one pass.

3. The Picture

   [3, 1, 5, 4, 2]   (value v → home index v-1)

   index 0 has 3 → 3's home is index 2. Swap.
   [5, 1, 3, 4, 2]
   index 0 now has 5 → 5's home is index 4. Swap.
   [2, 1, 3, 4, 5]
   index 0 now has 2 → 2's home is index 1. Swap.
   [1, 2, 3, 4, 5]
   index 0 has 1 → already home! Move on.
   ... rest are already home.

   Sorted in O(n)! ✅

4. 🔍 How to SPOT This Pattern

   Use Cyclic Sort when you see:
   ✅ Array of numbers in range 1..n  (or 0..n-1)
   ✅ "find the MISSING number"
   ✅ "find the DUPLICATE number"
   ✅ "find all numbers missing / all duplicates"
   ✅ "find the smallest missing positive"
   ✅ They ask for O(n) time AND O(1) extra space.

5. Why It's So Good for "Missing/Duplicate"

   After cyclic sort, every number SHOULD be at index value-1.
   Scan once: the FIRST index i where nums[i] != i+1 tells you
   the missing/misplaced number instantly.

   [1, 2, 4, 5, 6]  (should be 1..6, but...)
    ✓  ✓  ✗ ← index 2 holds 4, not 3 → 3 is MISSING

6. The Code Template 📝

   function cyclicSort(nums) {
     let i = 0;
     while (i < nums.length) {
       const home = nums[i] - 1;          // where nums[i] belongs
       if (nums[i] !== nums[home]) {
         [nums[i], nums[home]] = [nums[home], nums[i]];  // swap home
       } else {
         i++;                             // already correct → move on
       }
     }
     return nums;
   }

   // Find the missing number (range 1..n)
   function findMissing(nums) {
     cyclicSort(nums);
     for (let i = 0; i < nums.length; i++)
       if (nums[i] !== i + 1) return i + 1;   // first wrong spot
     return nums.length + 1;
   }

7. Practice Problems

   ⭐ core
   • Missing Number
   • Find All Numbers Disappeared in an Array

   ⭐⭐ Medium
   • Find the Duplicate Number
   • Find All Duplicates in an Array
   • First Missing Positive
   • Set Mismatch

8. ⚠️ Common Mistake

   ❌ Using `if (nums[i] !== i + 1)` as the swap condition. Compare
      by VALUE at the home slot: `nums[i] !== nums[home]`. This
      avoids infinite loops when there are duplicates.
   ❌ Trying to use cyclic sort when numbers AREN'T in a 1..n range.
      It only works for that bounded-range setup.

Key Takeaway

   Cyclic Sort = when numbers are 1..n, put each at index value-1
   by swapping. Then any out-of-place slot reveals the missing or
   duplicate number. O(n) time, O(1) space — a beautiful trick.

Next: Pattern #14 — Topological Sort, for ordering tasks with dependencies. 📋