← ~/lc-grind/posts

#268 - Missing Number

May 7, 2025

Missing Number

Problem Description

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

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 <= 104
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Solution

1. Problem Deconstruction

Technical Restatement:
Given an array nums of length n containing distinct integers in the range [0, n], find the single integer in [0, n] not present in nums.

Beginner Explanation:
You have a list of unique numbers. All numbers should cover every value from 0 to the length of the list, but one is missing. Your task is to identify which number is missing.

Mathematical Formulation:
Let ( S = {0, 1, 2, \ldots, n} ), and ( A \subset S ) with ( |A| = n ). Find ( x \in S \setminus A ).

Constraint Analysis:

  • ( n = \text{len}(nums) ): The range of numbers is determined by the array’s length.
  • ( 1 \leq n \leq 10^4 ): Solutions must handle large inputs efficiently (O(n) time).
  • ( 0 \leq \text{nums}[i] \leq n ): The missing number could be at the extremes (0 or ( n )).
  • All numbers are unique: Ensures exactly one missing number, allowing sum/XOR approaches.

Hidden Edge Cases:

  • Missing number is ( n ) (e.g., nums = [0,1] → output 2).
  • Missing number is 0 (e.g., nums = [1,2,3] → output 0).

2. Intuition Scaffolding

Real-World Metaphor:
A parking lot with numbered spots from 0 to N has all spots filled except one. Find the empty spot by checking which number is missing.

Gaming Analogy:
Collecting all keys numbered 0 to N to unlock a treasure chest. One key is missing; identify it by comparing your collection to the full set.

Math Analogy:
Given ( n+1 ) unique integers in arithmetic progression from 0 to ( n ), one term is omitted. Compute the missing term using properties of sums or bitwise operations.

Common Pitfalls:

  1. Forgetting the range is [0, n], not [0, n-1].
  2. Using O(n) space (e.g., hash tables) when O(1) is possible.
  3. Sorting the array (O(n log n)) instead of using arithmetic.
  4. Missing edge cases where the missing number is 0 or ( n ).

3. Approach Encyclopedia

1. Brute Force (Check Each Number):

def missingNumber(nums):
    n = len(nums)
    for num in range(n + 1):
        if num not in nums:
            return num

Time Complexity: ( O(n^2) ) (linear search for each number).
Space Complexity: ( O(1) ).

2. Sum Approach:

def missingNumber(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    actual = sum(nums)
    return expected - actual

Time Complexity: ( O(n) ) (summing the array).
Space Complexity: ( O(1) ).

3. XOR Approach:

def missingNumber(nums):
    xor = 0
    n = len(nums)
    for i in range(n + 1):
        xor ^= i
    for num in nums:
        xor ^= num
    return xor

Time Complexity: ( O(n) ) (two linear passes).
Space Complexity: ( O(1) ).

4. Cyclic Sort:

def missingNumber(nums):
    n = len(nums)
    for i in range(n):
        while nums[i] != i and nums[i] < n:
            correct_pos = nums[i]
            nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
    for i in range(n):
        if nums[i] != i:
            return i
    return n

Time Complexity: ( O(n) ) (each element is swapped once).
Space Complexity: ( O(1) ) (modifies input).

4. Code Deep Dive

Optimal Solution (Sum Approach):

def missingNumber(nums):
    n = len(nums)                     # 1. Get array length
    expected = n * (n + 1) // 2       # 2. Compute sum of 0..n
    actual = sum(nums)                # 3. Sum array elements
    return expected - actual          # 4. Difference is missing number

Edge Case Handling:

  • Example 1 (nums = [3,0,1]):
    expected = 6, actual = 4 → returns 2.
  • Example 2 (nums = [0,1]):
    expected = 3, actual = 1 → returns 2.
  • Missing 0 (nums = [1,2,3]):
    expected = 6, actual = 6 → returns 0 (handled by n=3, expected=6, actual=6 → 6-6=0).

5. Complexity War Room

Hardware-Aware Analysis:

  • For ( n = 10^4 ), the sum ( \frac{10^4 \times 10001}{2} = 50005000 ) fits in a 32-bit integer.

Industry Comparison Table:

Approach Time Space Readability Interview Viability
Brute Force O(n²) O(1) 8/10 ❌
Sum O(n) O(1) 10/10 ✅
XOR O(n) O(1) 7/10 ✅
Cyclic Sort O(n) O(1)* 6/10 ✅

6. Pro Mode Extras

Variants:

  • Two Missing Numbers: Use sum and sum of squares to derive two equations.
  • Missing Number in Sorted Array: Binary search for the first index where nums[i] != i.

Interview Cheat Sheet:

  • Key Insight: Use the arithmetic sum or XOR properties to avoid extra space.
  • Mention First: Always state time/space complexity before coding.
  • Edge Cases: Explicitly check for 0 and ( n ) as missing numbers.