268. Missing Number

Problem¶

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

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.

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 it 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.

Python solution¶

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

Comment on 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