Solution: Missing Number

Statement

Given an array, nums, containing nn distinct numbers in the range [0,n][0, n], return the only number in the range that is missing from the array.

Constraints:

  • n=n = nums.length
  • 1n1031 \leq n \leq 10^3
  • 00 \leq nums[i] n\leq n
  • 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 11 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 11 step forward each time. If the difference is greater than 1, our missing value would be the value of the first pointer ++ 11.

The time complexity for this approach becomes O(nlogn)+O(n)O(n \log n) + O(n). The space complexity is O(n)O(n).

Optimized approach using cyclic sort

Since our input contains unique numbers in the range 00 to nn, we can try placing them at their correct index. For example, we’ll place the number 11 on index 11, 22 on index 22, and so on. The first index with the incorrect value will be our missing number. If all numbers from 00 to n1n-1 are present, nn 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.