Missing Number

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 <= n <= 104

0 <= nums[i] <= n

All the numbers of nums are unique.

As a first approach, we can take a sort of “checklist” approach: make a list of all the numbers from 0 to $n$ , and then iterating through nums, remove each number from the checklist until there is only one left.

def missingNumber(self, nums: List[int]) -> int:
    all_nums = {i for i in range(len(nums) + 1)}

    for num in nums:
        if num in all_nums:
            all_nums.remove(num)

    return list(all_nums)[0]

How can we improve on this? A theme of array-based questions is to examine how the array itself can be used to solve this problem. Specifically, the array indices here also serve as a list of n distinct numbers in the range [0, n]! In fact, the indices contain the contiguous numbers

[0, 1, 2, \cdots, n - 1].

nums contains almost the same numbers, except one is replaced by $n$ . We can use this to our advantage: consider the sum of nums:

\begin{align*} \sum_{i \in \text{nums}} i &= \left(\sum^n_{i = 0} i\right) - x \\ &= \left(\sum^{n - 1}_{i = 0} i\right) + n - x \\ &= \left(\sum_{i \in \text{indices}} i \right) + n - x \\ \implies x &= n + \sum_{i \in \text{indices}} i - \sum_{i \in \text{nums}} i. \end{align*}

def missingNumber(self, nums: List[int]) -> int:
    res = len(nums)

    for i in range(len(nums)):
        res += i
        res -= nums[i]

    return res

Time Complexity

The algorithm has one loop with constant time iterations and $n$ iterations, so it is in $\mathcal{O}(n) time.

Space Complexity

The algorithm uses only one single integer variable, so it has constant space complexity.