268. Missing Number

Reformulated question¶

Given n distinct integers from the range [0, n], stored in an array of length n, find the single missing value.

Compact example:

nums = [3, 0, 1]
range = [0..3]
present = {0, 1, 3}
missing -> 2

Key Trick¶

Use the expected sum of 0..n and subtract the actual array sum.

\[ \text{missing} = \frac{n(n+1)}{2} - \sum(nums) \]

Trap¶

Forgetting the range is [0, n], not [0, n-1].
Using a set works but uses extra space, while the follow-up asks for \(O(1)\) extra space.
Sorting works but is \(O(n \log n)\), not optimal.
Missing 0 or missing n are the main edge cases.

Why Is This Question Interesting?¶

It tests whether you spot a simple invariant instead of overengineering.
It has multiple valid solutions:
- sum formula
- XOR
- sort/set
It checks comfort with edge cases and complexity tradeoffs.

Solution With Idiomatic Python¶

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        # There are n numbers, so the full range is 0..n.
        n = len(nums)

        # Sum of 0..n minus the actual sum leaves the missing number.
        return n * (n + 1) // 2 - sum(nums)

Library alternative:

None worth using here.
Built-ins already give the best direct interview solution.

Pytest Test¶

import pytest

@pytest.mark.parametrize(
    ("nums", "expected"),
    [
        ([3, 0, 1], 2),
        ([0, 1], 2),
        ([1], 0),
        ([0], 1),
        ([9, 6, 4, 2, 3, 5, 7, 0, 1], 8),
        ([4, 2, 1, 0], 3),
        ([5, 4, 3, 2, 1], 0),
        ([0, 1, 2, 3, 4], 5),
    ],
)
def test_missing_number(nums, expected):
    assert Solution().missingNumber(nums) == expected

Comment My Solution¶

Your solution is good.

It is correct.
It is optimal for the follow-up:
- \(O(n)\) time
- \(O(1)\) extra space
The comment is useful and short.
The test is fine, but add edge cases:
- missing 0
- missing n

import pytest

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        # 0 + 1 + 2 + ... + n = n(n + 1) / 2
        n = len(nums)
        return (n*(n + 1)) // 2 - sum(nums)

@pytest.mark.parametrize(
    ("nums", "missing"),
    [
        ([3,0,1], 2),
        ([0,1], 2),
        ([1], 0),
        ([9,6,4,2,3,5,7,0,1], 8),
    ]
)
def test_missingNumber(nums, missing):
    assert Solution().missingNumber(nums) == missing