Missing Number

Problem

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?

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.

Solution

We can use solutions like hashing etc. But this problem has special numbers in array.

Video explanation

Here is the video explaining below methods in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/2UnrXYCEMIg" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Using Sorting + linear search

A straightforward solution to this problem is to sort the array. When sorted, the numbers in the array should align with their respective indices since they range from 0 to n. For example, take the array nums = [3, 0, 1]. After sorting, it becomes nums = [0, 1, 3].

Once the array is sorted:

• Iterate through each element of the array and compare the value at each index with the index itself.
• If the value does not match its index, it indicates the missing number, which is the index.

If all numbers match their respective indices (e.g., nums = [0, 1, 2]), it means the missing number is n+1, because no number is missing within the valid range [0, n]. For example:

• Sorted array: nums = [0, 1, 2], and the indices 0, 1, 2 perfectly match the values in the array.
• In this case, the missing number is the next number 3, which is n+1.

Code

Java

class Solution {
    public int missingNumber(int[] nums) {
        // Sort the array
        Arrays.sort(nums);

        // Search for the missing number
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }

        // If no mismatch, missing number is n
        return nums.length;
    }
}

Python

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        # Sort the array
        nums.sort()

        # Search for the missing number
        for i in range(len(nums)):
            if nums[i] != i:
                return i

        # If no mismatch, missing number is n
        return len(nums)

Complexity

• ⏰ Time complexity: O(n log n) for sorting the array, and then traversing the array to check the mismatch takes O(n), overall: O(n log n).
• 🧺 Space complexity: O(1). Sorting the array may require additional space depending on the algorithm used, but we can assume constant space if we use in-place sorting algorithm like Quicksort.

Method 2 - Using Sorting + Binary Search

Once the array is sorted, we can optimise it further by using binary search, instead of performing a linear search. Binary search allows us to efficiently locate the missing number in the sorted array.

Here is the approach:

• Once the array nums is sorted, the missing number disrupts the sequence where index != nums[index].
• Use binary search:
  • Check at the middle index (mid) if nums[mid] == mid.
  • If they are equal, the missing number must be on the right half.
  • If they are not equal, the missing number must be on the left half.
• Continue narrowing down to find the missing index.

Code

Java

class Solution {
    public int missingNumber(int[] nums) {
        // Step 1: Sort the array
        Arrays.sort(nums);

        // Step 2: Apply binary search
        int low = 0, high = nums.length;

        while (low < high) {
            int mid = (low + high) / 2;

            // If the value matches the index, the missing number must be in the right half
            if (nums[mid] == mid) {
                low = mid + 1;
            } else {
                // Else, the missing number is in the left half
                high = mid;
            }
        }

        // Step 3: Return the position where the missing number should be
        return low;
    }
}

Python

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        # Step 1: Sort the array
        nums.sort()

        # Step 2: Apply binary search
        low, high = 0, len(nums)

        while low < high:
            mid = (low + high) // 2

            # If the value matches the index, the missing number is in the right half
            if nums[mid] == mid:
                low = mid + 1
            else:
                # Else, the missing number is in the left half
                high = mid

        # Step 3: Return the position where the missing number should be
        return low

Complexity

• ⏰ Time complexity: O(n log n) for sorting and O(log n) for finding missing element. Overall O(n log n)
• 🧺 Space complexity: O(n)

Method 3 - Counting Sort

A counting sort can be used, but it takes O(n + k) time and O(k) space, where k is the range. This is not optimal for large ranges, but is a valid approach for small N.

Method 4 - Using Hashset

A more effective approach to track the presence of elements is to use hashset. In hashset, we can insert and look up an element in just O(1) time. So, we add all the numbers from the array into a hashset and then verify which numbers in the range [0, n] (from 0 to n) are missing in the hashset.

For e.g. for this array, nums = [3,0,1], we add all elements to hashset hashset = {3, 0, 1}. Now, we iterate through the range [0, n] (where n = 3) and check which numbers are missing:

• 0 is in the HashSet ✅.
• 1 is in the HashSet ✅.
• 2 is not in the HashSet ❌ ⇨ the missing number is 2.

Code

Java

class Solution {
    public int missingNumber(int[] nums) {
        // Create a set to store elements
        HashSet<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        // Check for missing number in the range [0, n]
        int n = nums.length;
        for (int i = 0; i <= n; i++) {
            if (!numSet.contains(i)) {
                return i;
            }
        }

        // Should never reach here (problem guarantees a missing number)
        return -1;
    }
}

Python

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        # Create a set to store elements
        num_set: set[int] = set(nums)

        # Check for missing number in the range [0, n]
        for i in range(len(nums) + 1):
            if i not in num_set:
                return i

        # Should never reach here (problem guarantees a missing number)
        return -1

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(n)

Method 5 - Using Arithmetic Sum

Here is the approach:

1. Calculate the sum of the range [0, n] using the formula.
2. Sum up all the elements in the array.
3. Subtract the sum of the array from the sum of the range to get the missing number.

Method 6 - Using Arithmetic sum + Gaussian formula

This is a mathematical optimisation of the arithmetic sum approach where we explicitly rely on the Gaussian formula, simplifying the calculation further:

Code

Java

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;

        // Calculate the expected sum of the range [0, n]
        int sumExpected = n * (n + 1) / 2;

        // Calculate the actual sum of the elements in nums
        int sumActual = 0;
        for (int num : nums) {
            sumActual += num;
        }

        // The missing number is the difference between the expected and actual sums
        return sumExpected - sumActual;
    }
}

Python

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        n: int = len(nums)

        # Calculate the expected sum of the range [0, n]
        sum_expected: int = n * (n + 1) // 2

        # Calculate the actual sum of the elements in nums
        sum_actual: int = sum(nums)

        # The missing number is the difference between the expected and actual sums
        return sum_expected - sum_actual

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(1)

Method 7 - Using Arithmetic sum but avoid overflow

Large values of n can produce sums exceeding the integer limits, potentially causing overflow issues. We avoid this by summing numbers iteratively or simply calculating the difference directly during array traversal.

Here is the approach:

1. Instead of computing full sums, iterate and calculate the difference between each index in [0, n] and the corresponding array value.
2. Add the last index (n) in the range after completing the traversal.
3. This avoids creating large sums altogether, preventing overflow.

Code

Java

class Solution {
    public int missingNumber(int[] nums) {
        int missingNumber = 0;
        for (int i = 0; i < nums.length; i++) {
            missingNumber += (i - nums[i]);  // Add the difference iteratively
        }
        missingNumber += nums.length;  // Account for the final number in the range [0, n]
        return missingNumber;
    }
}

Python

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        missing_number = 0
        for i in range(len(nums)):
            missing_number += (i - nums[i])
        missing_number += len(nums)
        return missing_number

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(1)

Method 8 - Using XOR Operator

We know the following properties of XOR:

• x ^ x = 0 (cancels identical numbers).
• x ^ 0 = x (preserves a number when XORed with 0). All numbers XORed together, including the range [0, n] and elements of the array, will cancel out except for the missing number.

Approach

1. XOR all numbers in the range [0, n].
2. XOR all numbers in the array.
3. Combine the two XOR results to get the missing number (remaining unmatched due to cancellation).

Code

Java

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int xor = 0;
        for (int i = 0; i < n; i++) {
            xor ^= i ^ nums[i];
        }
        return xor ^ n;
    }
}

Python

class Solution(object):
    def missingNumber(self, nums):
        n = len(nums)
        xor_result = 0
        for i in range(n):
            xor_result ^= i ^ nums[i]
        return xor_result ^ n

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(1)