Missing Number

Patrick Leaton
Published: March 6, 2021, 10:37 p.m.
Problem Description

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.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

 

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Example 4:

Input: nums = [0]
Output: 1
Explanation: n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums.

Constraints:

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique.

 

The description was taken from https://leetcode.com/problems/missing-number/.

Problem Solution

#HashMap
#O(N) Time, O(N) Space
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        seen = {}
        for num in nums:
            seen[num] = True
        for i in range(len(nums)+1):
            if i not in seen:
                return i
 
#Math
#O(N) Time, O(1) Space
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        expected_sum = len(nums) * (len(nums) + 1) // 2
        actual_sum = sum(nums)
        return expected_sum - actual_sum

Problem Explanation

HashMap Solution

We can solve this problem by utilizing external memory to keep track of each number from the input array.  Afterward, while we iterate through the numbers we are expecting to see if any number is unaccounted for then we will return that number.

Let' start by initializing the dictionary that we will use to keep track of each number we have seen.

        seen = {}

 

For each number in the input array, we will mark it as seen.

        for num in nums:
            seen[num] = True

 

Then, for each number we are expecting to see, if that number hasn't been seen, we will return the number.

        for i in range(len(nums)+1):
            if i not in seen:
                return i

Math Solution

We can solve this problem by calculating the sum of the series and subtracting it by the sum of the array.  The difference in what should be there and what is there will give us the missing number.

The sum of the series is N*(N+1)/2, where N is the number of elements in the series, the length of the array in our case.  

        expected_sum = len(nums) * (len(nums) + 1) // 2

 

We can calculate the actual sum and return the difference.

The numbers present will be subtracted by themselves and will zero out, leaving just the number missing which was subtracted by zero.

        actual_sum = sum(nums)
        return expected_sum - actual_sum

 

Additional Notes

 

Easier Math Solution

Without calculating the sum of the series, the same optimal solution can be achieved by iterating through each number to N and adding each number to an expected sum variable, then subtracting the actual sum of the array by that.

#O(N) Time, O(1) Space
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        expected = 0
        for i in range(len(nums)+1):
            expected += i
        return expected - sum(nums)