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.
- n == nums.length
- 1 ≤ n ≤ 10⁴
- 0 ≤ nums[i] ≤ n
- All the numbers of nums are unique.
Example
nums = [3,0,1]2The array length is 3, so the numbers should be from 0 to 3 inclusive. The sum of numbers from 0 to 3 is 6. The sum of the given array is 4 (3 + 0 + 1). The missing number is 6 - 4 = 2.
Approach
Straightforward Solution
A brute-force approach would check for each number in [0, n] whether it exists in the array, resulting in O(n²) time complexity due to repeated membership checks.
Core Observation
The sum of the first n natural numbers (including zero) is n*(n+1)/2. The missing number can be found by subtracting the sum of the given array from this total sum.
Path to Optimal
Recognizing the arithmetic series sum formula allows transforming the problem into a simple subtraction: total sum minus sum of array elements. This reduces the time complexity to O(n) with O(1) space by iterating once over the array to compute the sum.
Optimal Approach
PreviewInitialize the result as n (the length of the array). Iterate through the array, adding the difference between the current index and the element at that index to the result…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
The solution iterates through the array once, performing constant time operations per element.
Space
O(1)
Only a fixed number of variables are used regardless of input size; no additional data structures are allocated.
Pattern Spotlight
Math & Geometry (Arithmetic Series Summation)
When a problem involves finding a missing or extra number in a sequence, leverage the known sum formula for the sequence and subtract the observed sum to identify the missing element in O(n) time and O(1) space.
Solution
| 1 | class Solution:
|
| 2 | def missingNumber(self, nums: list[int]) -> int:
|
| 3 | res = len(nums)
|
| 4 | for i in range(len(nums)):
|
| 5 | res += (i - nums[i])
|
| 6 | return res |
Step-by-Step Solution
Accumulate the Missing Number by Summing Index Differences
| 3 | res = len(nums)
|
| 4 | for i in range(len(nums)):
|
| 5 | res += (i - nums[i])
|
Objective
To compute the missing number by iterating through the array and accumulating the difference between indices and their corresponding values.
Key Insight
Starting with the result as the length of the array accounts for the missing number's upper bound. Adding (i - nums[i]) for each index i effectively computes the difference between the expected sum of indices and the actual sum of array elements in a single pass, avoiding separate sum computations and extra space.
Interview Quick-Check
Core Logic
The algorithm uses the formula result = n + sum(i) - sum(nums[i]) by accumulating differences in one pass, which identifies the missing number efficiently.
State & Boundaries
Iterate over all indices from 0 to n-1 to ensure every element and index contributes to the calculation.
Common Pitfalls & Bugs
Initializing result to zero instead of n would omit the missing number's upper bound, leading to incorrect results.
Complexity
This approach achieves O(n) time and O(1) auxiliary space, optimal for this problem.
Return the Computed Missing Number
To output the final missing number after completing the accumulation.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
res += (i - nums[i])Update the result by adding the difference between the current index and the element at that index.
This operation accumulates the net difference between the expected sum of indices and the actual sum of elements, isolating the missing number without separate sum calculations.
res = len(nums)Initialize the result variable with the length of the array.
Starting with n accounts for the missing number's upper bound in the range [0, n], enabling the algorithm to combine index and value differences into a single accumulator.
Full line-by-line criticality + rationale for all 4 lines available on Pro.
Test Your Understanding
Why does initializing the result with the length of the array help in finding the missing number?
See the answer with Pro.
Related Problems
Math & Geometry pattern
Don't just read it. Drill it.
Reconstruct Missing Number from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Missing Number drill