LeetCode 268: Missing Number - Complete Solutions Guide

Problem Statement

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.

Copy codeInput: nums = [3,0,1]
Output: 2
Explanation: n = 3, range [0,3] is missing 2

Input: nums = [0,1]
Output: 2
Explanation: n = 2, range [0,2] is missing 2

Solution 1: Hash Set (Intuitive)

Explanation

Store all numbers in a set, then check which number from 0 to n is missing: 1. Create Set: Add all numbers from array 2. Check Range: Look for missing number in 0..n 3. Return Result: The number not found in set

Step-by-Step Example

For nums = [3,0,1]: 1. Set: {0,1,3} 2. Check 0 → exists 3. Check 1 → exists 4. Check 2 → missing → return 2

Python Code

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

Complexity

• Time: O(n) - Creating set and checking range
• Space: O(n) - Storage for the set
• Pros: Easy to understand and implement

Solution 2: Gauss' Formula (Optimal)

Explanation

Use mathematical formula for sum of first n integers: 1. Calculate Expected Sum: n(n+1)/2 2. Calculate Actual Sum: Sum of array elements 3. Return Difference*: Missing number

Step-by-Step Example

For nums = [3,0,1]: 1. n = 3 → expected sum = 3*4/2 = 6 2. Actual sum = 3+0+1 = 4 3. Missing number = 6-4 = 2

Python Code

Copy codeclass 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) - Single pass to calculate sum
• Space: O(1) - Constant space
• Why Best: Most efficient mathematically

Key Insight

The sum of numbers from 0 to n is always n(n+1)/2. The difference between this and the array sum reveals the missing number.

Solution 3: Bit Manipulation (XOR)

Explanation

Leverage XOR properties: 1. Initialize Result: Start with array length (n) 2. XOR Operation: XOR result with all indices and values 3. Final Result: Missing number emerges from XOR operations

Step-by-Step Example

For nums = [3,0,1]: 1. Initialize: missing = 3 2. XOR with index 0: missing ^ 0 ^ 3 = 0 3. XOR with index 1: missing ^ 1 ^ 0 = 1 4. XOR with index 2: missing ^ 2 ^ 1 = 2 5. Final missing number: 2

Python Code

Copy codeclass 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) - Single pass through array
• Space: O(1) - Constant space
• Pros: No risk of integer overflow

Why XOR Works

XORing all numbers and indices cancels out existing pairs, leaving only the missing number.

Solution 4: Sorting (Alternative)

Explanation

Sort the array first, then find where the sequence breaks: 1. Sort Array: Arrange numbers in order 2. Check Sequence: Find first index where nums[i] ≠ i 3. Edge Case: If all match, missing number is n

Python Code

Copy codeclass 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 sort implementation
• Pros: Simple logic
• Cons: Slower than other solutions

Edge Cases to Consider

1. Missing 0: e.g., [1,2,3] → 0
2. Missing last number: e.g., [0,1,2] → 3
3. Single element: [0] → 1 or [1] → 0
4. Large array: Handle within constraints
5. All elements same: Impossible per problem constraints

Final Thoughts

• Interview Tip: Gauss' formula is the most elegant solution
• Key Insight: Mathematical properties can optimize search
• Follow-up: How would you find multiple missing numbers?