Missing Numbers Problem

Leetcode Lesson: Missing Number

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

Example 1: Input: nums = [3,0,1] Output: 2

Example 2: Input: nums = [0,1] Output: 2

Example 3: Input: nums = [9,6,4,2,3,5,7,0,1] Output: 8

Constraints:

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

2. Conceptual Understanding

This problem is about finding a missing element in a sequence. Imagine you have a set of numbered balls from 0 to n, but one ball is missing. Your task is to figure out which number is not in the set.

The key insight is that we know what the complete set should look like (all numbers from 0 to n), so we can compare what we have to what we should have.

3. Approach Brainstorming

Let's consider a few approaches:

  1. Sorting: Sort the array and check which number is missing.
  2. Hash Set: Use a set to store all numbers and then check which one is missing.
  3. Math: Use the formula for the sum of natural numbers and compare it with the actual sum.
  4. XOR: Utilize the XOR operation's properties to find the missing number.

Each approach has different trade-offs in terms of time and space complexity.

4. Optimal Solution Walkthrough

We'll focus on the mathematical approach, as it's efficient and introduces an interesting concept:

  1. Calculate the expected sum of numbers from 0 to n using the formula: n * (n + 1) / 2
  2. Calculate the actual sum of numbers in the given array
  3. The difference between these sums is the missing number

This approach is optimal because it requires only one pass through the array and uses a constant amount of extra space.

5. Python Implementation

def missingNumber(nums):
    n = len(nums)
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(nums)
    return expected_sum - actual_sum
  • len(nums) gives us n
  • n * (n + 1) // 2 calculates the sum of numbers from 0 to n
  • sum(nums) calculates the sum of numbers in the array
  • The difference is our missing number

6. Time and Space Complexity Analysis

Time Complexity: O(n)

  • We iterate through the array once to calculate the sum

Space Complexity: O(1)

  • We only use a constant amount of extra space, regardless of input size

This solution optimizes both time and space complexity.

7. Edge Cases and Testing

Consider these test cases:

  • [0] (missing number is 1)
  • [1] (missing number is 0)
  • [0, 1, 2, 3, 5] (missing number in the middle)
  • [0, 1, 2, 3, 4] (missing number is the last one, n)

8. Common Pitfalls and Mistakes

  • Forgetting that the range includes 0
  • Not handling the case where n is the missing number
  • Using integer division in languages where division defaults to floating-point (not an issue in Python 3)

9. Optimization Opportunities

Our solution is already quite optimal, but here's an alternative approach using XOR:

def missingNumber(nums):
    missing = len(nums)
    for i, num in enumerate(nums):
        missing ^= i ^ num
    return missing

This solution uses the properties of XOR to find the missing number in a single pass, without risk of integer overflow.

  • "Find the Duplicate Number" (similar concept but finding a duplicate instead of a missing number)
  • "Single Number" (uses XOR in a similar way)
  • Arithmetic sequences and sums

11. Reflection Questions

  1. How would you solve this problem if the numbers weren't in the range [0, n] but in [1, n+1]?
  2. Can you think of a real-world scenario where finding a missing number is important?
  3. How would the solution change if there were multiple missing numbers and you needed to find them all?

12. Additional Resources