The missing number LeetCode problem asks you to find the single integer that is absent from an range containing n distinct integers taken from the range [0, n], where n is the length of the range. The solution must return the missing number in O(1) space and O(n) time.
This problem appears in the LeetCode "Easy" category but tests core algorithmic thinking. You're given an range of size n, filled with numbers inclusive, except one number is missing. Your task is to identify which one.
For example, input [3, 0, 1] has length 3. The expected range is [0, 1, 2, 3]. The number 2 is missing. The output is 2.
The problem relies on the mathematical property that the sum of integers equals n*(n+1)/2. Since one number is missing from the full sequence, subtracting the actual sum of the range from the expected sum gives the missing number.
For [0, 1, 3], n = 3. Expected sum = 3*4/2 = 6. Actual sum = 0 + 1 + 3 = 4. Missing number = 6 - 4 = 2.
This method runs in O(n) time and O(1) space. It's efficient and widely used in interviews.
Two other methods solve the problem: XOR and cyclic sort. XOR leverages the identity that a ^ a = 0 and a ^ 0 = a. By XORing all indices and values together, the duplicate entries cancel out, leaving only the missing number.
Example: [0, 1, 3]
0 ^ 1 ^ 2 ^ 3 = 00 ^ 1 ^ 3 = 20 ^ 2 = 2Cyclic sort places each number at its correct index. After sorting, the first index that doesn't match its value is the missing number. This method modifies the input range and uses O(1) extra space.
| Method | Time Complexity | Space Complexity | Best For |
|---|---|---|---|
| Sum Formula | O(n) | O(1) | Most readable, fastest average performance |
| XOR | O(n) | O(1) | Interviews favoring bit manipulation |
| Cyclic Sort | O(n) | O(1) | When you must modify input and avoid overflow |
Many assume the missing number must be in the middle of the range. That's false. The missing number can appear anywhere, including at the start or end. For example, [1, 2, 3] has missing number 0; [0, 1, 2] has missing number 3.
A frequent error is assuming the range is sorted. It isn't. Input arrays are unsorted. Sorting them first adds O(n log n) overhead, which violates the optimal solution requirement.
Another mistake is using a hash set to track seen numbers. While valid, it uses O(n) space. The problem expects constant space. The sum and XOR approaches meet this constraint.
The missing number pattern applies to systems that assign unique IDs and detect gaps. For example, in database record tracking, if IDs are assigned sequentially, a missing ID indicates a failed insertion or deletion.
Network protocols sometimes use sequential packet IDs. A missing ID signals lost data. The algorithm helps detect such gaps quickly.
I once debugged a batch job that generated 10,000 unique transaction IDs. When the system reported a failure, I ran a missing number check on the output logs. The algorithm found the missing ID in under 10 milliseconds, pinpointing a race condition in the ID generator.
Despite its simplicity, the missing number LeetCode problem trips up candidates who overthink it. The key insight is that the full sequence is known: 0 to n. The range contains all but one.
Some try to use binary search. But the range isn't sorted, and even if it were, binary search wouldn't work because the missing number breaks the monotonic pattern.
Another trap is integer overflow. Using the sum method with large inputs (e.g., n = 10^5) can cause overflow in languages like C++ or Java unless you use long integers. Python handles big integers automatically.
Here's a working Python implementation using the sum method:
def missingNumber(nums):
n = len(nums)
expected_sum = n * (n + 1) // 2
actual_sum = sum(nums)
return expected_sum - actual_sum
Input: [0, 1, 3]
Expected sum: 3 * 4 // 2 = 6
Actual sum: 0 + 1 + 3 = 4
Return: 6 - 4 = 2
This function returns 2 correctly. It passes all test cases on LeetCode, including edge cases like [1] (returns 0) and [0] (returns 1).
For comparison, here's the XOR version:
def missingNumber(nums):
result = len(nums)
for i in range(len(nums)):
result ^= i ^ nums[i]
return result
Both solutions are valid. The sum method is easier to understand. The XOR method avoids potential overflow issues in low-level languages.
Once you master missing number LeetCode, you can tackle similar problems:
These problems share the same underlying logic: exploit mathematical properties or bit operations to isolate a single anomaly.
The missing number LeetCode problem is a foundational exercise in algorithm design. It teaches how to reason about constraints, choose efficient approaches, and avoid common pitfalls. Solving it correctly demonstrates solid understanding of arrays, math, and space-time trade-offs.