Cyclic Sort

Cyclic Sort is a pattern that applies to problems involving a range of integers (typically 1 to n). The idea is to place each element at its correct index in an array (i.e., at the index equal to its value minus one for 1-based arrays). This algorithm runs in O(n) time complexity and O(1) space complexity (ignoring input space), making it very efficient.

This technique works best when: - You are given an array of numbers ranging from 1 to n. - You need to reorder the numbers in place without using extra space.

Common Use Cases:

• Sorting arrays where elements are within a known range (1 to n).
• Finding missing or duplicate numbers in an array of integers in the range 1 to n.
• Cyclic sorting makes use of the fact that each number in the array can be directly mapped to an index.

How to Identify this Pattern in a Given Coding Question

You can identify this pattern in the following scenarios: - Known Range: The array contains numbers in a known range, usually from 1 to n. - Missing/Duplicate Numbers: The problem asks to find missing or duplicate numbers in an unsorted array. - Reordering without extra space: You are required to reorder elements of an array in place with minimal time and space.

Example Problem Types:

• Sort the array containing numbers from 1 to n with some missing or duplicate elements.
• Find all missing numbers in an unsorted array of numbers in the range 1 to n.
• Detect duplicates in a range of 1 to n.

Variations of the Cyclic Sort Technique

1. Simple Cyclic Sort: Sort an array in place where the numbers range from 1 to n.
2. Find Missing Number: Find one or more missing numbers in an unsorted array of size n with numbers from 1 to n.
3. Find Duplicate Numbers: Identify duplicates in an array that contains numbers from 1 to n.

Tricks to Keep in Mind

• Index Mapping: The key idea is that each number in the array should ideally be at an index equal to the number minus 1. For example, 1 should be at index 0, 2 at index 1, and so on.
• Swap Until Sorted: For each element, if it is not at its correct position, swap it with the element at its correct position. Repeat until all elements are in their correct positions.
• In-place Sorting: This algorithm works in place, meaning that you can reorder the array without using extra memory.
• Loop Through Once: Since each element will be swapped at most once, the time complexity remains O(n).

Common Coding Questions

Question 1: Simple Cyclic Sort

from typing import List

class CyclicSort:
    def cyclic_sort(self, nums: List[int]) -> List[int]:
        i = 0
        # Step 1: Traverse the list, trying to place each element in its correct index
        while i < len(nums):
            correct_index = nums[i] - 1  # For number `n`, the correct index is `n-1`
            
            # Step 2: If the element is not in its correct position, swap it
            if nums[i] != nums[correct_index]:
                nums[i], nums[correct_index] = nums[correct_index], nums[i]  # Swap to correct position
            else:
                i += 1  # Move to the next element if already in the correct position
        
        # Step 3: Return the sorted array
        return nums

# Example Usage:
nums = [3, 1, 5, 4, 2]
solution = CyclicSort()

sorted_nums = solution.cyclic_sort(nums)

print(sorted_nums)  # Output: [1, 2, 3, 4, 5]

Explanation of the Code:

1. Index Mapping: Each element is compared to its correct index (nums[i] - 1).
2. Swapping: If the element is not in its correct position, it is swapped with the element at its correct position.
3. In-place Sorting: This process continues until all elements are in their correct positions, achieving the sort in place.

Question 2: Finding Missing Numbers

from typing import List

class MissingNumbers:
    def find_missing_numbers(self, nums: List[int]) -> List[int]:
        i = 0
        # Step 1: Place each number at its correct index using cyclic sort
        while i < len(nums):
            correct_index = nums[i] - 1
            
            # Step 2: If the element is within the valid range and not at its correct position, swap it
            if 1 <= nums[i] <= len(nums) and nums[i] != nums[correct_index]:
                nums[i], nums[correct_index] = nums[correct_index], nums[i]
            else:
                i += 1
        
        # Step 3: After sorting, find all indices where the number is missing
        missing_numbers = []
        for i in range(len(nums)):
            if nums[i] != i + 1:
                missing_numbers.append(i + 1)
        
        return missing_numbers

# Example Usage:
nums = [3, 7, 1, 2, 8, 4, 5]
solution = MissingNumbers()
missing = solution.find_missing_numbers(nums)
print(missing)  # Output: [6]

Explanation of the Code:

1. Cyclic Sort to Rearrange: First, rearrange the numbers using cyclic sort.
2. Detect Missing Numbers: After sorting, any index where the number doesn’t match i + 1 is considered missing, and those indices represent the missing numbers.

Question 3: Finding Duplicate Numbers

from typing import List

class FindDuplicates:
    def find_duplicates(self, nums: List[int]) -> List[int]:
        i = 0
        duplicates = []
        
        # Step 1: Place each number at its correct index
        while i < len(nums):
            correct_index = nums[i] - 1
            
            # Step 2: If the number is not in its correct position, swap it
            # but only if it's different from the number in the correct position
            if nums[i] != nums[correct_index]:
                nums[i], nums[correct_index] = nums[correct_index], nums[i]
            else:
                i += 1
        
        # Step 3: Check the list for duplicates
        for i in range(len(nums)):
            if nums[i] != i + 1:
                duplicates.append(nums[i])
        
        return duplicates

# Example Usage:
nums = [4, 3, 2, 7, 8, 2, 3, 1]
solution = FindDuplicates()
duplicates = solution.find_duplicates(nums)
print(duplicates)  # Output: [2, 3]

Explanation of the Code:

1. Cyclic Sort: The array is sorted in place using cyclic sort.
2. Identify Duplicates: After sorting, if an element is not in its correct position (i + 1), it indicates a duplicate.