Missing Number

Difficulty: Easy | Acceptance: 72.00% | Paid: No Topics: Array, Hash Table, Math, Binary Search, Bit Manipulation, Sorting

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.

• Examples
• Constraints
• Approach 1: Sorting
• Approach 2: Hash Set
• Approach 3: Math Sum
• Approach 4: Bit Manipulation
• Approach 5: Binary Search

Examples

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.

Constraints

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

Sorting

Intuition If we sort the array, the numbers should be in the order 0, 1, 2, …, n. We can iterate through the sorted array and check if the current number matches its index. The first index where nums[i] != i is the missing number. If all match, the missing number is n.

Steps

• Sort the input array nums.
• Iterate through the array with index i from 0 to n - 1.
• If nums[i] is not equal to i, return i.
• If the loop completes without returning, return n.

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        nums.sort()
        for i in range(len(nums)):
            if nums[i] != i:
                return i
        return len(nums)

Complexity

• Time: O(n log n) due to sorting.
• Space: O(1) or O(n) depending on the sorting algorithm’s memory usage.
• Notes: Modifies the original array.

Hash Set

Intuition We can use a hash set to store all the numbers present in the array. Then, we iterate through the range [0, n] and check which number is not present in the set.

Steps

• Initialize an empty hash set.
• Add all numbers from nums into the set.
• Iterate i from 0 to n.
• If i is not in the set, return i.

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        num_set = set(nums)
        for i in range(len(nums) + 1):
            if i not in num_set:
                return i
        return -1

Complexity

• Time: O(n) for set operations.
• Space: O(n) to store the set.
• Notes: Uses extra memory proportional to the input size.

Math Sum

Intuition The sum of the first n integers (from 0 to n) can be calculated using the formula n * (n + 1) / 2. If we subtract the sum of the elements in the array from this expected sum, the result is the missing number.

Steps

• Calculate n as the length of the array.
• Calculate the expected sum of numbers from 0 to n using the formula.
• Calculate the actual sum of the numbers in the array.
• Return expected_sum - actual_sum.

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        n = len(nums)
        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)
        return expected_sum - actual_sum

Complexity

• Time: O(n) to sum the array.
• Space: O(1).
• Notes: Be careful of integer overflow in languages like Java or C++ if n is large. Use long or long long.

Bit Manipulation

Intuition We can use the XOR operation. XOR has the property that a ^ a = 0 and a ^ 0 = a. If we XOR all indices from 0 to n and all numbers in the array, all pairs will cancel out except for the missing number.

Steps

• Initialize missing to n.
• Iterate i from 0 to n - 1.
• Update missing by XOR-ing it with i and nums[i].
• Return missing.

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        missing = len(nums)
        for i, num in enumerate(nums):
            missing ^= i ^ num
        return missing

Complexity

• Time: O(n).
• Space: O(1).
• Notes: Avoids potential integer overflow issues associated with the Math Sum approach.

Binary Search

Intuition If we sort the array first, we can observe a pattern: if no number is missing before index i, then nums[i] should be equal to i. If a number is missing before index i, then nums[i] will be greater than i. We can use binary search to find the smallest index i where nums[i] > i.

Steps

• Sort the array nums.
• Initialize left = 0 and right = nums.length - 1.
• While left <= right:
  • Calculate mid = left + (right - left) / 2.
  • If nums[mid] > mid, the missing number is on the left (including mid), so set right = mid - 1.
  • Else, the missing number is on the right, so set left = mid + 1.
• After the loop, left will point to the missing number.

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        nums.sort()
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > mid:
                right = mid - 1
            else:
                left = mid + 1
        return left

Complexity

• Time: O(n log n) due to sorting.
• Space: O(1) or O(n) depending on the sorting algorithm.
• Notes: Less efficient than Math or XOR approaches due to sorting, but demonstrates the application of binary search.