Cyclic Sort Pattern

Introduction

The Cyclic Sort pattern is an efficient in-place sorting technique primarily used for arrays containing numbers within a specific, contiguous range (e.g., 1 to N). It ensures that each number is eventually placed at its correct sorted position without using auxiliary space.

Quick Overview

Iterate through an array, placing each element at its correct sorted index (value - 1) by repeatedly swapping it until it's in place, then moving to the next element.

Motivation

Traditional comparison-based sorts like Merge Sort or Quick Sort achieve O(N log N) time complexity. However, for problems involving arrays with numbers in a fixed range (e.g., 1 to N), we can achieve linear O(N) time complexity. The Cyclic Sort pattern provides this optimization, making it ideal for finding missing numbers, duplicates, or sorting such arrays when auxiliary space is restricted to O(1).

Core Idea

The fundamental idea is that if an array contains distinct numbers from 1 to N, each number 'X' should ideally reside at index 'X-1'. The algorithm iterates through the array. For each element nums[i], it determines its correct index j = nums[i] - 1. If nums[i] is not already at nums[j], it swaps nums[i] with nums[j]. This process repeats for nums[i] until it is correctly positioned, only then does the algorithm increment i to process the next element.

Key Insight

The 'aha!' moment is realizing that by continuously placing an out-of-place element nums[i] into its correct position nums[nums[i]-1], we don't necessarily increment i. Instead, the element that was swapped into nums[i] is now at the current index i, and it also needs to be checked and potentially moved to its correct position. This guarantees that each number makes at most one 'full cycle' of swaps to reach its final spot, leading to O(N) time complexity.

Requirements

• The array must contain (or be expected to contain) numbers within a specific, positive, contiguous range, typically from 1 to N (or 0 to N-1).
• The pattern is most effective when working with integers and often assumes no duplicates or requires specific handling for them.
• It's an in-place algorithm, meaning it modifies the input array directly.

Dry Run

Let's trace nums = [3, 1, 5, 4, 2] (numbers 1 to 5):

• Initial state: nums = [3, 1, 5, 4, 2], i = 0

• Iteration 1: i = 0, nums[0] = 3.

  • Correct index for 3 is 3 - 1 = 2.
  • nums[0] (3) is not equal to nums[2] (5). Swap nums[0] and nums[2].
  • nums becomes [5, 1, 3, 4, 2]. i remains 0.

• Iteration 2: i = 0, nums[0] = 5.

  • Correct index for 5 is 5 - 1 = 4.
  • nums[0] (5) is not equal to nums[4] (2). Swap nums[0] and nums[4].
  • nums becomes [2, 1, 3, 4, 5]. i remains 0.

• Iteration 3: i = 0, nums[0] = 2.

  • Correct index for 2 is 2 - 1 = 1.
  • nums[0] (2) is not equal to nums[1] (1). Swap nums[0] and nums[1].
  • nums becomes [1, 2, 3, 4, 5]. i remains 0.

• Iteration 4: i = 0, nums[0] = 1.

  • Correct index for 1 is 1 - 1 = 0.
  • nums[0] (1) is equal to nums[0] (1). It's in its correct place.
  • Increment i to 1.

• Iteration 5: i = 1, nums[1] = 2.

  • Correct index for 2 is 2 - 1 = 1.
  • nums[1] (2) is equal to nums[1] (2). It's in its correct place.
  • Increment i to 2.

• Iteration 6: i = 2, nums[2] = 3.

  • Correct index for 3 is 3 - 1 = 2.
  • nums[2] (3) is equal to nums[2] (3). It's in its correct place.
  • Increment i to 3.

• Iteration 7: i = 3, nums[3] = 4.

  • Correct index for 4 is 4 - 1 = 3.
  • nums[3] (4) is equal to nums[3] (4). It's in its correct place.
  • Increment i to 4.

• Iteration 8: i = 4, nums[4] = 5.

  • Correct index for 5 is 5 - 1 = 4.
  • nums[4] (5) is equal to nums[4] (5). It's in its correct place.
  • Increment i to 5.

• Loop terminates: i = 5, which is N. The array is sorted: [1, 2, 3, 4, 5].

Algorithm

• Initialize a pointer i to 0, representing the current index being examined.
• Get the length of the array, N.
• While i is less than N:
• Calculate correct_idx = nums[i] - 1. (This assumes numbers are 1-based, i.e., in the range [1, N]. For 0-based range [0, N-1], correct_idx = nums[i].)
• Check if nums[i] is a valid number for the expected range (e.g., 1 <= nums[i] <= N). If not, or if duplicates are present and need special handling, this step might be modified.
• If nums[i] is within the valid range AND nums[i] is not at its correct_idx (i.e., nums[i] != nums[correct_idx]):

•    Swap `nums[i]` with `nums[correct_idx]`.
  

• Else (if nums[i] is already at its correct position, or is out of range/duplicate):

•    Increment `i` to move to the next element.
  

Pseudocode

function cyclicSort(nums): n = length of nums i = 0 while i < n: # Determine the target index for the number at nums[i] # Assuming numbers are in range [1, N] correct_idx = nums[i] - 1

    # Check if nums[i] is a valid number to place (e.g., within 1 to N range)
    # and if it's not already in its correct position.
    # This handles out-of-range numbers and prevents infinite loops on duplicates.
    if 1 <= nums[i] <= n and nums[i] != nums[correct_idx]:
        # Swap nums[i] with the element at its correct_idx
        temp = nums[i]
        nums[i] = nums[correct_idx]
        nums[correct_idx] = temp
    else:
        # If nums[i] is correctly placed, or invalid, or a duplicate
        # (depending on specific problem requirements), move to the next index.
        i = i + 1
return nums

Code

(See Implementations block below)

Line-by-Line Explanation

• Line 5: Initializes the index i to 0. This pointer will traverse the array from left to right.
• Line 6: Gets the total number of elements in the array, stored in n.
• Line 7: The main loop continues as long as i is within the array bounds. i is only incremented when the element at nums[i] is correctly placed or cannot be placed by this pattern.
• Line 10: Calculates the correct_idx for the number nums[i]. If numbers are in the range [1, N], then correct_idx = value - 1. For example, 1 should be at index 0, 2 at index 1, etc.
• Line 16: This condition checks three things: 1) 1 <= nums[i] <= n: Ensures the current number nums[i] is within the expected range [1, N]. Numbers outside this range (e.g., 0, negative, or >N) cannot be placed by this pattern and should be skipped or handled differently based on the problem. 2) nums[i] != nums[correct_idx]: Checks if the number nums[i] is not already at its correct position. This is crucial to avoid infinite swaps if nums[i] is already correct, or if duplicates are present where nums[i] equals nums[correct_idx] but is not the 'correct' one (e.g., [3, 1, 3] where nums[0]=3, correct_idx=2, and nums[2] is also 3).
• Line 18: If the conditions are met, it means nums[i] is out of place. We swap nums[i] with the element that is currently at correct_idx. After the swap, the element nums[i] contains the number that was previously at correct_idx, and this new nums[i] still needs to be checked (hence i is not incremented).
• Line 20: If the if condition is false (meaning nums[i] is either out of range, a duplicate that can't be placed this way, or already in its correct_idx), we simply move to the next element by incrementing i.

Time Complexity

O(N) - Each number is swapped at most once to its correct position. While there's a while loop nested with a potential swap, i increments only when nums[i] is in its correct place. Each element nums[k] is involved in a swap at most once to move it to k's final position. If nums[i] is not in its correct position, it is swapped, but i is not incremented. The crucial insight is that each misplaced number is put into its correct place in one swap. Even though an element might be swapped multiple times before it settles, it moves closer to its target position or its target position is moved towards it. The total number of swaps and comparisons will be proportional to N. Thus, the algorithm makes at most 2N swaps and N increments of i, resulting in O(N) overall time complexity.

Space Complexity

O(1) - The algorithm operates entirely in-place, modifying the input array directly without using any additional data structures whose size scales with the input size. Only a few constant-space variables (like i, n, correct_idx, temp) are used.

Advantages

• Optimal Time Complexity: Achieves O(N) time complexity, which is often the best possible for array traversal problems.
• Optimal Space Complexity: Uses O(1) auxiliary space as it's an in-place algorithm.
• Simplicity: Relatively straightforward to implement for its specific use cases.
• Versatility: Can be adapted to solve various problems like finding missing numbers, duplicates, and smallest missing positive integers.

Limitations

• Specific Range Requirement: Only applicable when array elements are within a specific, contiguous range (e.g., 1 to N or 0 to N-1). It doesn't work for arbitrary integer ranges or floating-point numbers.
• Modifies Input Array: The algorithm performs an in-place sort, which means it alters the original array. If the original array state must be preserved, a copy is needed (which would increase space complexity).
• Duplicate Handling: Requires careful modification when dealing with duplicates, as the core logic assumes each number has a unique 'correct' slot. Without modifications, duplicates can lead to infinite loops or incorrect placement if not handled (e.g., nums[i] == nums[correct_idx] check helps mitigate this).
• Negative/Zero/Large Numbers: Numbers outside the expected positive range [1, N] must be handled as edge cases or skipped, as they don't have a 'correct' place within the 1 to N indices.

Common Mistakes

• Incorrectly calculating correct_idx: For a 1-based range [1, N], the correct index is value - 1. For a 0-based range [0, N-1], it's value.
• Incrementing i prematurely: After a swap, the element nums[i] has changed and must be re-evaluated before moving to i+1. Increment i only when nums[i] is correctly placed or is an unplaceable element.
• Forgetting range checks: Not validating 1 <= nums[i] <= n can lead to IndexError (out-of-bounds access) or incorrect behavior with negative numbers or numbers larger than N.
• Infinite loops with duplicates: If nums[i] == nums[correct_idx] but nums[i] is a duplicate and not the actual element that should be at correct_idx, directly swapping can cause an infinite loop. The nums[i] != nums[correct_idx] check is vital.
• Not handling edge cases: Empty arrays, single-element arrays, or arrays with numbers outside the expected range.

Edge Cases

• Empty array: [] - The loop condition i < n will immediately be false, and the function will correctly return an empty array or do nothing.
• Single-element array: [1] - Loop runs once, nums[0]=1, correct_idx=0. nums[0] is already correct, i increments. Sorted.
• Already sorted array: [1, 2, 3, 4, 5] - Each nums[i] will immediately satisfy nums[i] == nums[correct_idx], so i increments N times. O(N) in this case too.
• Array with elements in reverse order: [5, 4, 3, 2, 1] - Triggers many swaps, demonstrating the full O(N) behavior.
• Arrays containing numbers outside the expected range [1, N]: E.g., [0, 1, 3] for N=3. The 1 <= nums[i] <= n check handles this by skipping 0.
• Arrays with duplicates: E.g., [1, 3, 3]. For finding missing, this works. For finding all duplicates, the pattern needs adjustment post-sort or during sort to identify elements not in their correct spot or duplicates at correct spot.
• Arrays with only valid numbers but some are duplicates and some are missing: E.g., [2, 3, 1, 4, 3] (missing 5, duplicate 3).

Recognition Tricks

• Problems asking to sort an array containing numbers in a specific range (e.g., 1 to N or 0 to N-1).
• Problems requiring O(N) time complexity and O(1) space complexity for sorting or related tasks.
• Finding missing numbers in a sequence.
• Finding duplicate numbers in a sequence.
• Finding the first missing positive integer.
• Rearranging elements such that nums[i] holds a specific value derived from i (e.g., i+1).
• When a direct hash map / set approach is too slow or uses too much space, and the range constraint exists.

When To Use

• When the input array consists of numbers from a restricted, contiguous positive range (e.g., 1 to N, or 0 to N-1).
• To sort an array in-place with O(N) time and O(1) space complexity.
• To efficiently find missing numbers within a given range in an array.
• To efficiently find duplicate numbers within a given range in an array.
• To find the smallest missing positive integer in an array.
• When solving problems that leverage the property of numbers having a 'correct' index based on their value.

Alternative Approaches

• Comparison Sorts (e.g., Merge Sort, Quick Sort): O(N log N) time, O(N) or O(log N) space. General-purpose but less efficient for the specific constraints of Cyclic Sort problems.
• Hash Set/Map: O(N) time, O(N) space. Can find missing/duplicates but uses auxiliary space. Good for arbitrary ranges or non-integer data.
• Boolean Array/Frequency Array: O(N) time, O(N) space. Similar to hash maps, used to mark presence of numbers. Limited by range and value size.
• Bit Manipulation: O(N) time, O(1) space. Can be used for finding single missing/duplicate numbers by XORing, but less versatile for multiple missing/duplicates or sorting.
• Counting Sort: O(N + K) time, O(K) space (where K is the range of numbers). Efficient for specific ranges but uses O(K) space, which can be large if K is large.

Interview Perspective

Interviewers love the Cyclic Sort pattern because it showcases a candidate's ability to identify opportunities for optimal O(N) time and O(1) space solutions beyond generic sorting. It demonstrates a deep understanding of array manipulation and leveraging inherent properties of data. Be prepared to explain the correct_idx logic, the while loop condition (when to increment i), and how the nums[i] != nums[correct_idx] check prevents infinite loops. You should also be ready to adapt the pattern for variations like handling duplicates, finding missing numbers, or dealing with out-of-range values, making it clear how the conditions 1 <= nums[i] <= n are crucial.

Key Takeaways

• Cyclic Sort is an O(N) time, O(1) space in-place sorting algorithm for numbers in a specific range (typically 1 to N).
• Its core principle is to place each number X at its designated index X-1.
• The pointer i only advances when nums[i] is correctly positioned (or unplaceable by this method).
• It's a powerful pattern for problems involving missing numbers, duplicates, and smallest missing positives.
• Careful handling of edge cases, out-of-range numbers, and duplicates (using nums[i] != nums[correct_idx]) is essential for a robust implementation.

Practice Problems

(See Practice Problems index below)

class Solution {
public:
    void cyclicSort(std::vector<int>& nums) {
        int i = 0;
        int n = nums.size();
        while (i < n) {
            int correct_idx = nums[i] - 1;

            if (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[correct_idx]) {
                std::swap(nums[i], nums[correct_idx]);
            } else {
                i++;
            }
        }
    }
};