Cyclic Sort for Missing and Duplicate Numbers

Hello! In our previous lesson, we mastered the Merge Intervals pattern, an excellent technique for handling problems with overlapping ranges. We saw how sorting the input is often the key that unlocks an efficient solution. Today, we're diving into the final topic of this module: Cyclic Sort.

Cyclic Sort is another unique, array-based pattern, but it solves a very different class of problems. It's a highly efficient, in-place method specifically designed for situations where an array contains numbers from a contiguous range, like 1 to n. Its real power isn't just in sorting, but in what the 'sorted' array reveals. This pattern is a favorite in technical interviews because it tests your ability to manipulate an array in-place to achieve O(n) time and O(1) space complexity. Our goal today is to understand the core mechanics of Cyclic Sort and then, crucially, use it to find missing numbers, duplicates, and other data errors in an array.

1. The Core Idea: Placing Numbers in Their Correct Homes

The fundamental principle of Cyclic Sort is simple but powerful. If you have an unsorted array of length n that is supposed to contain all numbers from 1 to n, then in the sorted version, each number k should reside at index k-1.

• The number 1 should be at index 0.
• The number 2 should be at index 1.
• ...and the number n should be at index n-1.

The Cyclic Sort algorithm iterates through the array and enforces this rule. For each element it visits, it checks if the element is at its correct index. If not, it swaps the element with the one that is currently at its correct destination. A key detail is that we only move our pointer forward when the number at the current position is already correct.

This process continues until every number is in its "home" position. Let's visualize this with an example.

The following video provides an excellent, energetic walkthrough of this exact process. It will help you build a strong intuition for the algorithm's flow.

2. The Algorithm and Its Efficiency

As you saw in the video, the algorithm can be summarized as follows:

1. Initialize a pointer i = 0.
2. While i is less than the length of the array:
   a. Determine the correct index j for the value at nums[i]. For a 1-based range (1 to n), this is j = nums[i] - 1.
   b. If the number at nums[i] is not already at its correct index (nums[i] != nums[j]), swap them. Do not increment i. The new number at nums[i] needs to be checked.
   c. If the number at nums[i] is already at its correct index, increment i to move to the next position.
3. The array is now "cyclically sorted."

You might wonder about the time complexity. With a while loop that doesn't always increment its pointer, it could seem like it might be worse than O(n). However, the key insight is that each number is swapped into its correct, final position at most once. Once a number is in its correct spot, it's never moved again. This guarantees that the total number of swaps is at most n-1. Therefore, the overall time complexity is O(n). Since we modify the array in-place, the space complexity is O(1).

The following article gives a fantastic, concise explanation of this.

3. Applying the Pattern: The Real Goal

In interviews and real-world problems, you rarely use Cyclic Sort just to sort an array. Standard sorting algorithms are more general. The true utility of Cyclic Sort is as a pre-processing step to quickly identify irregularities in an array that should contain a contiguous range of numbers. After running the sort, a simple linear scan can reveal missing numbers, duplicates, or other errors.

This is the most critical part of the lesson. The following resource is perfectly structured to teach this, presenting five common interview problems that all build on the same core Cyclic Sort pattern.

Let's break down the logic for two of these variations, which are especially common.

Finding All Missing Numbers (Duplicates allowed)

• Problem: Given an array with numbers from the range [1, n], but with some duplicates, find all the numbers from 1 to n that are missing.
• Solution:
  1. Perform the standard Cyclic Sort. Because of duplicates, some numbers won't end up in their correct places. For example, if you have two 3s and no 5, one 3 will end up at index 2, but the other 3 will likely end up in the place where 5 should have been (index 4).
  2. After the sort, iterate through the array from i = 0 to n-1.
  3. If nums[i] != i + 1, it means the number that should be here (i + 1) is missing. Add i + 1 to your list of missing numbers.

Finding the Corrupt Pair (One Duplicate, One Missing)

• Problem: An array that should contain numbers from 1 to n has an error: one number was duplicated, and one number is missing. Find both.
• Solution:
  1. Perform the standard Cyclic Sort.
  2. After the sort, iterate through the array. You will find exactly one position i where nums[i] != i + 1.
  3. The number at this incorrect position, nums[i], is the duplicate. It's the number that "stole" the spot.
  4. The number that should have been at this position, i + 1, is the missing number.
  5. Return both nums[i] and i + 1.

As you can see, once you understand the core pattern, these seemingly complex problems become simple variations on a theme. Recognizing when an array problem involves a contiguous range is the key to knowing when to apply Cyclic Sort.

Conclusion

This lesson concludes our first module on advanced algorithmic patterns for arrays and lists. With Cyclic Sort, you've added a powerful and efficient tool to your problem-solving arsenal. It exemplifies how understanding the constraints and properties of your input data (like a contiguous range of numbers) can lead to highly optimized, in-place solutions—a skill that is highly valued in scalable system design and technical interviews.

Key Takeaways:

• When to Use: Apply Cyclic Sort to problems involving arrays of length n that contain numbers in a specific range, typically 1 to n or 0 to n-1.
• Core Logic: The pattern works by placing each number k at its "correct" index (k-1 for a 1-based range). You iterate, swap any misplaced number into its correct spot, and only advance your pointer when the current position holds the correct value.
• The Payoff: The primary use of Cyclic Sort is not the sorting itself, but the "mismatches" left after the sort. A second linear scan can then easily identify missing numbers, duplicates, or both, all in O(n) time and O(1) space.

We have now covered the Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, and Cyclic Sort patterns. In our next lesson, we will begin a new module, "Advanced Algorithmic Patterns: Heaps and Searching," starting with the Top K Elements pattern, which uses a different data structure—the heap—to solve another common class of problems.