Cyclic Sort

Cyclic Sort Pattern

Introduction

Cyclic Sort is a pattern that deals with problems involving arrays containing numbers in a given range. It’s particularly useful when you have numbers from 1 to N or 0 to N-1. The beauty of this pattern lies in its ability to sort in O(n) time complexity with O(1) space complexity.

Why Learn This Pattern?

1. Efficiency Benefits

   • O(n) time complexity
   • O(1) space complexity
   • In-place sorting
   • Minimal number of writes

2. Common Applications

   • Finding missing numbers
   • Finding duplicate numbers
   • Array permutations
   • Range-based array problems
   • Data integrity verification

Understanding Cyclic Sort

1. Core Principle The main idea is that each number should be at its correct position:

   For 1 to N: number i should be at index (i-1)
   For 0 to N-1: number i should be at index i
   
   Example (1 to N):
   Input:  [3, 1, 5, 4, 2]
   Output: [1, 2, 3, 4, 5]
   
   Example (0 to N-1):
   Input:  [2, 0, 4, 1, 3]
   Output: [0, 1, 2, 3, 4]
   

2. How It Works

   # Visual representation of sorting [3, 1, 5, 4, 2]
   
   Step 1: [3, 1, 5, 4, 2] → swap 3 to index 2
          [5, 1, 3, 4, 2]
   
   Step 2: [5, 1, 3, 4, 2] → swap 5 to index 4
          [2, 1, 3, 4, 5]
   
   Step 3: [2, 1, 3, 4, 5] → swap 2 to index 1
          [1, 2, 3, 4, 5]
   
   Result: [1, 2, 3, 4, 5]
   

Basic Implementation

1. Standard Cyclic Sort For arrays containing numbers from 1 to N:

   def cyclicSort(nums):
       """
       Sort array containing numbers 1 to N
       Time Complexity: O(n)
       Space Complexity: O(1)
       """
       i = 0
       while i < len(nums):
           correct_pos = nums[i] - 1  # For 1 to N
           if nums[i] != nums[correct_pos]:
               nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
           else:
               i += 1
       return nums
   
   # Example:
   # Input: [3, 1, 5, 4, 2]
   # Output: [1, 2, 3, 4, 5]
   

2. Zero-Based Cyclic Sort For arrays containing numbers from 0 to N-1:

   def cyclicSort(nums):
       """
       Sort array containing numbers 0 to N-1
       Time Complexity: O(n)
       Space Complexity: O(1)
       """
       i = 0
       while i < len(nums):
           correct_pos = nums[i]  # For 0 to N-1
           if nums[i] < len(nums) and nums[i] != nums[correct_pos]:
               nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
           else:
               i += 1
       return nums
   
   # Example:
   # Input: [2, 0, 4, 1, 3]
   # Output: [0, 1, 2, 3, 4]
   

Detailed Examples with Step-by-Step Solutions

1. Complete Example: Finding Missing Number Problem: Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing.

   Input: nums = [3, 0, 1]
   Target: Find the missing number
   
   Step-by-step solution:
   
   Initial array: [3, 0, 1]
   
   Step 1: i = 0, nums[0] = 3
          3 should be at index 3, but that's out of bounds
          Skip since 3 >= len(nums)
          [3, 0, 1]  i++
   
   Step 2: i = 1, nums[1] = 0
          0 should be at index 0, swap with 3
          [0, 3, 1]  i++
   
   Step 3: i = 2, nums[2] = 1
          1 should be at index 1, swap with 3
          [0, 1, 3]  i++
   
   Final array: [0, 1, 3]
   
   Check indices: 
   index 0: nums[0] = 0 ✓
   index 1: nums[1] = 1 ✓
   index 2: nums[2] = 3 ✗ (should be 2)
   
   Therefore, 2 is missing
   

2. Complete Example: Finding Duplicate Problem: Find the duplicate number in an array of n+1 integers where each integer is in the range [1, n].

   Input: nums = [1, 3, 4, 2, 2]
   Target: Find the duplicate number
   
   Step-by-step solution:
   
   Initial array: [1, 3, 4, 2, 2]
   
   Step 1: i = 0, nums[0] = 1
          1 should be at index 0
          Already correct, i++
          [1, 3, 4, 2, 2]
   
   Step 2: i = 1, nums[1] = 3
          3 should be at index 2, swap
          [1, 4, 3, 2, 2]
   
   Step 3: i = 1, nums[1] = 4
          4 should be at index 3, swap
          [1, 2, 3, 4, 2]
   
   Step 4: i = 1, nums[1] = 2
          2 should be at index 1
          Already correct, i++
          [1, 2, 3, 4, 2]
   
   Step 5: i = 2, nums[2] = 3
          3 should be at index 2
          Already correct, i++
          [1, 2, 3, 4, 2]
   
   Step 6: i = 3, nums[3] = 4
          4 should be at index 3
          Already correct, i++
          [1, 2, 3, 4, 2]
   
   Step 7: i = 4, nums[4] = 2
          2 should be at index 1
          But nums[1] is already 2
          Found duplicate: 2
   

3. Complete Example: First Missing Positive Problem: Find the smallest missing positive integer in an unsorted array.

   Input: nums = [3, 4, -1, 1]
   Target: Find first missing positive integer
   
   Step-by-step solution:
   
   Initial array: [3, 4, -1, 1]
   
   Step 1: i = 0, nums[0] = 3
          3 should be at index 2, swap
          [−1, 4, 3, 1]
   
   Step 2: i = 0, nums[0] = -1
          Skip negative number, i++
          [−1, 4, 3, 1]
   
   Step 3: i = 1, nums[1] = 4
          4 should be at index 3, swap
          [−1, 1, 3, 4]
   
   Step 4: i = 1, nums[1] = 1
          1 should be at index 0, but skip since nums[0] < 0
          i++
          [−1, 1, 3, 4]
   
   Step 5: i = 2, nums[2] = 3
          3 should be at index 2
          Already correct, i++
          [−1, 1, 3, 4]
   
   Step 6: i = 3, nums[3] = 4
          4 should be at index 3
          Already correct, i++
          [−1, 1, 3, 4]
   
   Check indices starting from 1:
   index 0 should have 1: missing
   index 1 has 1: present
   index 2 has 3: present
   index 3 has 4: present
   
   Therefore, 2 is the first missing positive integer
   

4. Complete Example: Find All Missing Numbers Problem: Find all numbers that are missing from an array containing n numbers in range [1, n].

   Input: nums = [4, 3, 2, 7, 8, 2, 3, 1]
   Target: Find all missing numbers
   
   Step-by-step solution:
   
   Initial array: [4, 3, 2, 7, 8, 2, 3, 1]
   
   Step 1: i = 0, nums[0] = 4
          4 should be at index 3, swap
          [7, 3, 2, 4, 8, 2, 3, 1]
   
   Step 2: i = 0, nums[0] = 7
          7 should be at index 6, swap
          [3, 3, 2, 4, 8, 2, 7, 1]
   
   Continue swapping until no more valid swaps possible...
   Final array: [1, 2, 3, 4, 3, 2, 7, 8]
   
   Check each index:
   index 0: nums[0] = 1 ✓
   index 1: nums[1] = 2 ✓
   index 2: nums[2] = 3 ✓
   index 3: nums[3] = 4 ✓
   index 4: nums[4] = 3 ✗ (should be 5)
   index 5: nums[5] = 2 ✗ (should be 6)
   index 6: nums[6] = 7 ✓
   index 7: nums[7] = 8 ✓
   
   Therefore, missing numbers are [5, 6]
   

Common Problem Patterns

1. Find Missing Number Find the missing number in an array containing n distinct numbers in range [0, n].

   Key insight: After sorting, the first number that’s not at its correct index is missing.

   def findMissing(nums):
       """
       Time Complexity: O(n)
       Space Complexity: O(1)
       """
       i = 0
       while i < len(nums):
           correct_pos = nums[i]
           if nums[i] < len(nums) and nums[i] != nums[correct_pos]:
               nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
           else:
               i += 1
       
       # Find first number not in correct position
       for i in range(len(nums)):
           if nums[i] != i:
               return i
       return len(nums)
   
   # Example:
   # Input: [3, 0, 1]
   # Output: 2
   

2. Find All Missing Numbers Find all missing numbers in an array containing numbers from 1 to n.

   def findAllMissing(nums):
       """
       Time Complexity: O(n)
       Space Complexity: O(1)
       """
       i = 0
       while i < len(nums):
           correct_pos = nums[i] - 1
           if nums[i] != nums[correct_pos]:
               nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
           else:
               i += 1
       
       missing = []
       for i in range(len(nums)):
           if nums[i] != i + 1:
               missing.append(i + 1)
       return missing
   
   # Example:
   # Input: [4, 3, 2, 7, 8, 2, 3, 1]
   # Output: [5, 6]
   

3. Find Duplicate Number Find the duplicate number in an array containing n+1 numbers from 1 to n.

   def findDuplicate(nums):
       """
       Time Complexity: O(n)
       Space Complexity: O(1)
       """
       i = 0
       while i < len(nums):
           correct_pos = nums[i] - 1
           if nums[i] != nums[correct_pos]:
               nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
           else:
               if i != correct_pos:
                   return nums[i]
               i += 1
       return -1
   
   # Example:
   # Input: [1, 3, 4, 2, 2]
   # Output: 2
   

Advanced Variations

1. Find All Duplicates Find all duplicates in an array where each number appears once or twice.

   def findAllDuplicates(nums):
       duplicates = []
       i = 0
       while i < len(nums):
           correct_pos = nums[i] - 1
           if nums[i] != nums[correct_pos]:
               nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
           else:
               i += 1
       
       for i in range(len(nums)):
           if nums[i] != i + 1:
               duplicates.append(nums[i])
       return duplicates
   
   # Example:
   # Input: [4, 3, 2, 7, 8, 2, 3, 1]
   # Output: [2, 3]
   

2. First Missing Positive Find the smallest missing positive number in an unsorted array.

   def firstMissingPositive(nums):
       i = 0
       n = len(nums)
       
       # Ignore non-positive and numbers greater than n
       while i < n:
           correct_pos = nums[i] - 1
           if 0 < nums[i] <= n and nums[i] != nums[correct_pos]:
               nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
           else:
               i += 1
       
       # Find first missing positive number
       for i in range(n):
           if nums[i] != i + 1:
               return i + 1
       return n + 1
   
   # Example:
   # Input: [3, 4, -1, 1]
   # Output: 2
   

Edge Cases and Common Pitfalls

1. Input Validation

   • Empty array
   • Single element array
   • Array with all same elements
   • Array with negative numbers
   • Array with numbers out of range

2. Common Mistakes

   • Forgetting to handle zero-based vs one-based indexing
   • Not handling duplicates properly
   • Incorrect position calculation
   • Infinite loops in swap logic

3. Performance Considerations

   • Minimize number of swaps
   • Handle edge cases efficiently
   • Consider input size constraints

Practice Problems

1. Basic

   • Sort array with numbers 1 to N
   • Find missing number
   • Find duplicate number

2. Intermediate

   • Find all missing numbers
   • Find all duplicates
   • First missing positive

3. Advanced

   • Find corrupt pair
   • Find smallest missing positive
   • K missing positive numbers

Key Takeaways

1. When to Use

   • Numbers in range 1 to N or 0 to N-1
   • Need in-place sorting
   • Looking for missing/duplicate elements
   • Space complexity is a constraint

2. Advantages

   • O(n) time complexity
   • O(1) space complexity
   • Minimal number of writes
   • In-place algorithm

3. Limitations

   • Only works with specific number ranges
   • Not suitable for general sorting
   • May not handle duplicates well
   • Requires modifiable array

Remember: The key to solving cyclic sort problems is to:

1. Identify the number range
2. Use correct position formula
3. Handle edge cases properly
4. Consider duplicates carefully
5. Minimize number of swaps