Solution: Missing Number
Let's solve the Missing Number problem using the Cyclic Sort pattern.
Statement
Given an array, nums, containing distinct numbers in the range , return the only number in the range that is missing from the array.
Constraints:
-
nums.length
-
nums[i]
- There are no duplicates in the array.
Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.
Naive approach
A naive approach would be to first sort the array using quick sort and then traverse the array with two adjacent pointers. Since the integers are sorted, the difference between two adjacent array elements should be if there is no missing integer. We can start by having the first pointer at index 0
and the second pointer at index 1
, moving both step forward each time. If the difference is greater than 1, our missing value would be the value of the first pointer .
The time complexity for this approach becomes . The space complexity is .
Optimized approach using cyclic sort
Since our input contains unique numbers in the range to , we can try placing them at their correct index. For example, we’ll place the number on index , on index , and so on. The first index with the incorrect value will be our missing number. If all numbers from to are present, is the missing number.
An efficient approach would be to sort the elements in-place. We can iterate over the array elements one at a time. If the current number is not at its correct index, we swap it with the number at its correct index. This is a classic example of cyclic sort. Hence, the problem fits naturally under the cyclic sort pattern.
We’ll iterate over the array elements to place them in the correct positions. Once the array is sorted, we’ll compare the elements with their indices. If the two are not equal, the missing number will be the index of that element.
Visualize the above algorithm below:
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.