Cyclic Sort

What you'll learn

• The Golden Rule

  Use cyclic sort when: - You have numbers in a known range (typically [0, n] or [1, n]) - You need to find missing, duplicate, or corrupt numbers - You want O(n) time and O(1) space The key insight: if numbers are in range [1, n], each nu…

• The Swap-to-Correct-Index Pattern

• Core Algorithm

  For an array of n numbers in range [1, n]: - Number 1 should be at index 0 - Number 2 should be at index 1 - Number k should be at index k - 1 Iterate through the array. At each position, repeatedly swap the current number to its correct…

• Base Implementation

  ---

• Find the Missing Number

  Problem: Array of n numbers containing values from [0, n] with exactly one missing. Since range is [0, n], number v belongs at index v (not v-1). ---

• Find All Missing Numbers

  Problem: Array of n numbers from range [1, n], some duplicated, find all missing. After sorting, any index i where nums[i] != i + 1 means i + 1 is missing. ---

• Find the Duplicate Number

  Problem: Array of n+1 numbers in range [1, n] with exactly one duplicate. When we try to swap a number to its correct position but that position already holds the same value — we have found the duplicate. ---

• Find All Duplicates

  Problem: Array of n numbers from [1, n] where some appear twice. After sorting, any position where the value does not match the expected value — that value is a duplicate (it is displaced because its home is occupied by its other copy). ---

• Find the Corrupt Pair

  Problem: Array of n numbers from [1, n] where one number is missing and one is duplicated. Find both. ---

• Smallest Missing Positive

  Problem: Given an array of integers (positive, negative, zero, possibly duplicates), find the smallest positive integer (starting from 1) that does not appear in the array. Must be O(n) time and O(1) extra space. Examples: - [1, 3, 6, 4]…

• First K Missing Positive Numbers

  Problem: Given an unsorted array and a number k, find the first k missing positive numbers. ---

• Complexity Analysis

  | Problem | Time | Space | |---------|------|-------| | Cyclic sort | O(n) | O(1) | | Find missing number | O(n) | O(1) | | Find all missing | O(n) | O(1) | | Find duplicate | O(n) | O(1) | | Find all duplicates | O(n) | O(1) | | Find co…

• Pattern Recognition Checklist

  Ask yourself: 1. Are the numbers in a range [0, n] or [1, n]? 2. Am I looking for missing, duplicate, or corrupt numbers? 3. Can I use the index as the "home" for each number? 4. Do I need O(1) space? If yes → cyclic sort is likely the o…