Given an array of n distinct numbers taken from the range 0 to n, return the one number in that range that is missing.
Before you code
List the time and extra space of each approach before writing any of them: sorting and scanning, a hash set of the values, the sum formula, and XOR.
Hints
- Sorting: O(n log n) time. A hash set: O(n) time, O(n) space.
- The numbers 0 to n add up to n(n + 1)/2. Subtract the array's sum to get the missing one: O(n) time, O(1) space. In languages with fixed-width integers, think about whether the sum can overflow.
- XOR avoids overflow entirely: XOR all indexes 0 to n and all values together. Every number that is present cancels out, as in Single number.
Production & complexity notes
When solving Missing number on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Space and hidden costs to reinforce the underlying pattern.
What it practices
Choosing between solutions by both time and extra memory, from Space and hidden costs.