LeetCode 268 - Missing Number

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Math, Binary Search, Bit Manipulation, Sorting

Solution

Problem Understanding

The problem gives an array nums containing n distinct integers. Every number is supposed to come from the range [0, n], which means there are actually n + 1 possible values in total. Since the array only contains n numbers, exactly one value from that range is missing.

The task is to identify and return that missing number.

For example, if nums = [3,0,1], the array length is 3, so the valid range is [0,3]. The numbers present are 0, 1, and 3, therefore the missing value is 2.

An important detail is that all numbers are unique. This guarantee simplifies the problem because we never need to handle duplicates or ambiguous cases. The constraints are also relatively small, n <= 10^4, so multiple approaches are feasible. However, the follow up explicitly asks for an O(n) time solution with O(1) extra space, which guides us toward a mathematical or bit manipulation based solution.

Several edge cases are important to consider:

The missing number could be 0, meaning the sequence starts at 1.
The missing number could be n, meaning all smaller values are present.
The array is not guaranteed to be sorted.
A naive implementation that repeatedly scans the array for each possible number could become inefficient.

Because the array contains exactly one missing value and every other number appears exactly once, we can leverage properties of arithmetic sums or XOR operations to solve the problem efficiently.

Approaches

Brute Force Approach

The most straightforward solution is to check every number from 0 to n and determine whether it exists in the array.

One way to do this is:

For each candidate number in the range [0, n]
Scan the entire array
If the candidate is not found, return it

This works because the problem guarantees exactly one missing value. Eventually, the missing number will be the only value not encountered during a scan.

However, this approach is inefficient because for each of the n + 1 possible numbers, we may scan up to n elements. This produces O(n^2) time complexity.

A slightly improved brute force method uses a hash set:

Insert all numbers into a set
Check each number from 0 to n
Return the first number not in the set

This reduces time complexity to O(n) but requires O(n) extra space.

Optimal Approach

The optimal solution uses the mathematical formula for the sum of the first n integers.

The key observation is:

The numbers from 0 to n should have a total sum of:

$0 + 1 + 2 + \dots + n = \frac{n(n+1)}{2}$

If we compute this expected sum and subtract the actual sum of the array, the difference must be the missing number.

For example:

Expected sum for n = 3:

$\frac{3(3+1)}{2} = 6$

Actual array sum for [3,0,1] is 4
Missing number is 6 - 4 = 2

This approach is optimal because:

We only iterate through the array once
We use constant extra memory
The runtime is linear

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly scans the array for each possible number
Optimal	O(n)	O(1)	Uses expected sum minus actual sum

Algorithm Walkthrough

Determine the value of n by taking the length of the array.

The problem guarantees that the valid numbers should come from the range [0, n], so the array length directly tells us the upper bound of the expected sequence. 2. Compute the expected sum of all integers from 0 to n.

Instead of generating the entire sequence, use the arithmetic series formula:

$\text{expectedSum} = \frac{n(n+1)}{2}$

This gives the total sum that would exist if no number were missing. 3. Compute the actual sum of the numbers in the array.

Iterate through nums and accumulate the values. 4. Subtract the actual sum from the expected sum.

Since every number except one is present exactly once, all shared values cancel out, leaving only the missing number. 5. Return the difference.

Why it works

The algorithm relies on the fact that the array contains every number from 0 to n except one. The expected sum includes all numbers, while the actual sum excludes exactly one value. Therefore:

$\text{missing} = \text{expectedSum} - \text{actualSum}$

All present numbers effectively cancel out, leaving only the missing value.

Python Solution

from typing import List

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)

        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)

        return expected_sum - actual_sum

The implementation begins by computing n, which represents both the array length and the maximum possible value in the expected range.

Next, the code computes the theoretical sum of all numbers from 0 to n using the arithmetic formula. Integer division // is used because the result is always an integer.

The built in sum() function calculates the total of the values actually present in the array.

Finally, subtracting the actual sum from the expected sum isolates the missing number and returns it directly.

The solution is concise because the mathematical observation eliminates the need for extra data structures or nested loops.

Go Solution

func missingNumber(nums []int) int {
    n := len(nums)

    expectedSum := n * (n + 1) / 2

    actualSum := 0
    for _, num := range nums {
        actualSum += num
    }

    return expectedSum - actualSum
}

The Go implementation follows the same logic as the Python version.

Instead of using a built in summation function, Go requires an explicit loop to accumulate the array values. The range keyword iterates through the slice efficiently.

Go integers are sufficient for the given constraints because the maximum possible sum is small relative to integer limits. Since n <= 10^4, overflow is not a concern.

An empty slice is also handled naturally, although the constraints guarantee at least one element.

Worked Examples

Example 1

Input:

nums = [3,0,1]

The array length is 3, so the valid range is [0,3].

Expected sum:

$\frac{3(3+1)}{2} = 6$

Actual sum calculation:

Step	Current Number	Running Sum
Start	-	0
1	3	3
2	0	3
3	1	4

Final calculation:

6 - 4 = 2

Output:

Example 2

Input:

nums = [0,1]

The array length is 2, so the valid range is [0,2].

Expected sum:

$\frac{2(2+1)}{2} = 3$

Actual sum calculation:

Step	Current Number	Running Sum
Start	-	0
1	0	0
2	1	1

Final calculation:

3 - 1 = 2

Output:

Example 3

Input:

nums = [9,6,4,2,3,5,7,0,1]

The array length is 9, so the valid range is [0,9].

Expected sum:

$\frac{9(9+1)}{2} = 45$

Actual sum calculation:

Step	Current Number	Running Sum
Start	-	0
1	9	9
2	6	15
3	4	19
4	2	21
5	3	24
6	5	29
7	7	36
8	0	36
9	1	37

Final calculation:

45 - 37 = 8

Output:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The array is traversed once to compute the sum
Space	O(1)	Only a few integer variables are used

The runtime is linear because each array element is processed exactly once. No nested loops or repeated scans occur.

The space complexity is constant because the algorithm does not allocate any extra data structures proportional to input size. Only a fixed number of variables are maintained regardless of n.

Test Cases

from typing import List

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)
        return expected_sum - actual_sum

solution = Solution()

assert solution.missingNumber([3, 0, 1]) == 2       # basic example
assert solution.missingNumber([0, 1]) == 2          # missing largest number
assert solution.missingNumber([9,6,4,2,3,5,7,0,1]) == 8  # unsorted input

assert solution.missingNumber([1]) == 0             # missing zero
assert solution.missingNumber([0]) == 1             # single element, missing n

assert solution.missingNumber([0,2]) == 1           # missing middle value
assert solution.missingNumber([1,2]) == 0           # missing first value
assert solution.missingNumber([0,1,2,3,4]) == 5    # missing last value

assert solution.missingNumber([5,4,3,2,1,0]) == 6  # reverse ordered input
assert solution.missingNumber([2,0,3,1,5]) == 4    # random ordering

Test	Why
`[3,0,1]`	Standard example with missing middle value
`[0,1]`	Missing largest possible number
`[9,6,4,2,3,5,7,0,1]`	Larger unsorted input
`[1]`	Smallest size with missing zero
`[0]`	Smallest size with missing `n`
`[0,2]`	Missing value between two present numbers
`[1,2]`	Missing first element
`[0,1,2,3,4]`	Missing last element
`[5,4,3,2,1,0]`	Reverse ordered input
`[2,0,3,1,5]`	Random ordering validation

Edge Cases

One important edge case occurs when the missing number is 0. This can easily break implementations that assume the sequence always starts with zero present. For example, with nums = [1,2], the expected range is [0,2], and the algorithm correctly computes the missing value because the expected sum still includes zero.

Another important case is when the missing number is n, the largest value in the range. For example, nums = [0,1,2] should return 3. Some implementations accidentally iterate only up to n - 1 and fail to consider the upper bound. The arithmetic formula naturally includes n, so this implementation handles the case correctly.

A third edge case is unordered input. The array is not guaranteed to be sorted, so solutions relying on adjacency comparisons without sorting can fail. The sum based approach is independent of order because addition is commutative. Whether the numbers are sorted, reversed, or randomly arranged, the result remains correct.

Another subtle case is the minimum valid input size. With arrays such as [0] or [1], there is only one number present and one missing value. The implementation still works because the expected sum formula remains valid even for very small n.