Identify
- problems involving a sorted array with numbers in a given range
- find the missing/duplicate/smallest number in a sorted/rotated array
Motive
- as we know, the input array contains numbers in the range of 0 to n, we can use this fact to devise an efficient way to sort the numbers
- since all numbers are unique, we can try placing each number at its correct place, for example, placing 0 at index 0, placing 1 at index 1, and so on
- once we have every number in its correct place, we can iterate the array to find the index which does not have the correct number, and that index will be our missing number
- since the array will have n numbers, which means array indices will range from 0 to n-1. Therefore, we will ignore the number n as we can’t place it in the array, so => nums[i] < len(nums)
Steps
- iterate over the array one number at a time, and if the current number you are iterating is not at the correct index, you swap it with the number at its correct index
- you could try placing the number in its correct index, but this will produce a complexity of O(n^2) which is not optimal, hence the Cyclic Sort pattern of O(n)
Complexity
Time O(n) = O(n) + **O(n - 1)**
Space O(1)
Common Problems