268. Missing Number

Description

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

Intuition

The intuition behind solving the missing number problem is to recognize that if we had all the numbers from 0 to n, their sum would be the sum of the first n natural numbers. By comparing this expected sum with the actual sum of numbers in the array, we can identify the missing number.

Alternatively, we can also check each number from 0 to n and determine which one is not present in the array.

Approach

1. Initial Setup: - Determine the length of the array n, which tells us the range of numbers that should be present from 0 to n.
2. Iterative Check: - Iterate through all numbers from 0 to n. - For each number i, calculate the difference diff = n - i. - Check if diff is present in the array. If it is not found, that is the missing number, so return diff.
3. Edge Case: - If no missing number is found during the iteration (which theoretically should not happen given valid inputs), return -1.

Complexity

Time Complexity:

O(n^2) for the C++ and Python solutions that use linear search to check if each diff is present in the array. The Java solution improves this to O(n) by using a HashSet for constant-time lookups.

Space Complexity:

• C++/Python: O(1) since no additional data structures are used.
• Java:O(n) due to the usage of a HashSet to store all elements of the array.

Code

C++

class Solution {
public:
    int missingNumber(std::vector& nums) {
        int n = nums.size();
        
        for (int i = 0; i <= n; i++) {
            int diff = n - i;
            
            if (std::find(nums.begin(), nums.end(), diff) == nums.end()) {
                return diff;
            }
        }
        return -1;
    }
};

Python

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

Java

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        Set numSet = new HashSet<>();
        
        for (int num : nums) {
            numSet.add(num);
        }
        
        for (int i = 0; i <= n; i++) {
            int diff = n - i;
            
            if (!numSet.contains(diff)) {
                return diff;
            }
        }
        return -1;
    }
}

JavaScript

var missingNumber = function(nums) {
    let n= nums.length
    
    for(let i=0; i<=n; i++){
        const diff = n - i
        
        if(!nums.includes(diff)) return diff
    }
    return -1
};