Missing Number — Day 88(Python)

Photo by Gabriel Valdez on Unsplash

Today’s question is easy-tagged. It from Leetcode’s Daily Coding Challenge — March edition.

268. 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.

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 <= 104
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

One way to solve this problem is by sorting the given array, then using a variable that starts from 0 and increments itself while checking if all the numbers are present in the array.

Let us look into the code snippet.

class MissingNumberFinder:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()
        i = 0
        for num in (nums):
            if i == num:
                i += 1
            else:
                return i
        return i

Complexity analysis.

Time Complexity

Since we are sorting our array, the time complexity to sort is O(NlogN).

Space Complexity

Space complexity is O(1).

Is it possible to improve the time complexity? Can we use maybe some extra data structure to solve this problem?

We can use an array that is initialized with -1. What should the size of the array be? Since we are expected to have all the numbers from 0 to n, the size of the array should be n + 1, or in other words length of array + 1. After initialization, go through each number from the input array, these numbers will be the index in our extra array. In these indexes, replace -1 with the current index. Then go through the extra data structure and check if any of the indexes have -1. Those indexes with -1 are the missing numbers.

Let us look into the code snippet.

class MissingNumberFinder:
    def missingNumber(self, nums: List[int]) -> int:
        extra_nums = [-1 for i in range(len(nums)+1)]
        for num in nums:
            extra_nums[num] = num
        for num in range(len(extra_nums)):
            if extra_nums[num] == -1:
                return num
        return len(nums)

Complexity analysis.

Time Complexity

Since we are just traversing through the array, the time complexity is O(N)

Space Complexity

Since we are using an extra data structure of size N, the space complexity is O(N).

Is there a way to improve the space complexity?

Bit manipulation is another way to solve this problem. I had to read through leetcode’s solution to understand this.

When we XOR a number with itself, we get 0 as output. Can we leverage this information? Since we are expected to have numbers from 0 to N, we can XOR each number with its index and look for missing number.

Let us look into the code snippet.

class MissingNumberFinder:
    def missingNumber(self, nums: List[int]) -> int:
        missing_num = len(nums)
        for i in range(len(nums)):
            missing_num ^= i ^ nums[i]
        return missing_num

Complexity analysis.

Time Complexity

Since we are just traversing through the array, the time complexity is O(N)

Space Complexity

Space complexity is O(1).