Solution: Missing Number

Statement

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

Constraints:

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

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

Optimized approach using cyclic sort

The intuition behind using this approach uses the unique property where each element should match its index, given data in a specific range. The algorithm starts by sorting the array so that each element is placed in its correct position (i.e., its value matches its index). After sorting, the first instance where an element does not match its index indicates the missing number.

Let’s walkthrough the detailed steps of this algorithm: