The Cyclic Sort pattern is an efficient technique used primarily for problems involving arrays containing numbers in a given range. Typically, if an array of length n contains numbers from 1 to n (or 0 to n-1), Cyclic Sort can be used to arrange these numbers into their correct sorted positions in linear time.

Core Idea:

The main idea is to iterate through the array, and for each element, place it at its correct index. If the element at the current index i is x, its correct position should be at index x-1 (if the numbers are from 1 to n) or x (if numbers are from 0 to n-1).

  1. Iterate through the array, element by element.
  2. For the current element nums[i], determine its correct position, let’s say j.
  3. If nums[i] is not already at nums[j], swap nums[i] with nums[j].
  4. Repeat step 3 for the new nums[i] (the element that was swapped into this position) until nums[i] is the correct element for index i (i.e., nums[i] == i+1 or nums[i] == i).
  5. Only then move to the next index i+1.

This process continues until all numbers are in their correct sorted positions. Because each number is placed in its correct spot at most once, the overall time complexity is O(n).

Common Scenarios & How it Works:

  1. Sorting an Array with Numbers in a Specific Range:
    • When you have an array of n numbers and you know these numbers are in the range [1, n] or [0, n-1] (possibly with duplicates or missing numbers).
    • The goal is to sort the array. After applying Cyclic Sort, the element k will be at index k-1 (or k).
  2. Finding the Missing Number:
    • Given an array of n-1 numbers from the range [1, n], find the missing number.
    • Apply Cyclic Sort. After sorting, iterate through the array. The first index i where nums[i] != i+1 indicates that i+1 is the missing number. If all numbers are in place, the missing number is n.
  3. Finding All Missing Numbers:
    • Similar to finding one missing number, but you collect all indices i where nums[i] != i+1.
  4. Finding the Duplicate Number:
    • If an array of n+1 numbers contains numbers from [1, n] with one duplicate.
    • During Cyclic Sort, if you encounter nums[i] and find that nums[i] is already present at its correct position nums[nums[i]-1], then nums[i] is the duplicate. (Careful with the condition to avoid infinite loops if nums[i] == nums[nums[i]-1]).
    • Alternatively, after Cyclic Sort, the number at an index i that is not i+1 and whose value is already at its correct position indicates a duplicate.
  5. Finding All Duplicate Numbers:
    • Similar to finding one duplicate, but collect all such numbers.
  6. Finding the Smallest Missing Positive Number (LeetCode #41):
    • A more complex variation where the array can contain negative numbers and numbers larger than n. You first might need to segregate positive numbers and then apply Cyclic Sort to the relevant part of the array.

Advantages:

  • Efficiency: Typically achieves O(n) time complexity.
  • In-Place: Usually sorts the array with O(1) extra space.
  • Simplicity: The core logic of placing elements in their correct positions is relatively intuitive.

When to Use:

  • When you are given an array of numbers that should ideally fall into a consecutive range (e.g., 1 to n).
  • Problems that ask to find missing numbers, duplicate numbers, or to sort an array with these specific range properties.
  • When an in-place sort with O(n) time complexity is desired for such specific arrays.

Example LeetCode Problems:

  1. (#268) Missing Number
  2. (#448) Find All Numbers Disappeared in an Array
  3. (#287) Find the Duplicate Number
  4. (#442) Find All Duplicates in an Array
  5. (#41) First Missing Positive (More advanced, requires careful handling)
  6. (#645) Set Mismatch (Find the duplicate and the missing number)
  7. (#765) Couples Holding Hands (Can be modeled as a cyclic sort problem)