The Cyclic Sort pattern is used when dealing with an array containing numbers in a given range. It involves iterating through the array and placing each number at its correct index by swapping elements. Here's an example to help you understand the pattern better:
Problem: Given an unsorted array containing numbers from 1 to n with one number missing, find the missing number.
Example:
Input: [4, 2, 3, 1, 6] Output: 5
In this problem, the array should contain numbers from 1 to n, but the number 5 is missing. We can solve this problem using the Cyclic Sort pattern as follows:
def find_missing_number(nums): i = 0 while i < len(nums): correct_index = nums[i] - 1 # Calculate the index where the current number should be if nums[i] != nums[correct_index]: # If the number is not at its correct index, swap nums[i], nums[correct_index] = nums[correct_index], nums[i] else: i += 1 # Find the missing number for i in range(len(nums)): if nums[i] != i + 1: return i + 1 # If no missing number found, return n + 1 return len(nums) + 1
Let's analyze the code:
i
pointer to 0 and iterate through the array.nums[i]
, we calculate the correct index where it should be placed (nums[i] - 1
).len(nums) + 1
as the missing number (since all numbers from 1 to n are present).Now, let's test the function using the example input:
nums = [4, 2, 3, 1, 6] missing_number = find_missing_number(nums) print(missing_number) # Output: 5
The missing number is correctly identified as 5 using the Cyclic Sort pattern.
The Cyclic Sort pattern can be applied to solve various other problems, such as finding the smallest missing positive number, finding all missing numbers, or finding duplicate numbers. The underlying idea remains the same - placing each number at its correct index using swaps.