Missing Number

Problem in Plain English

Find the one number missing from an array that holds n distinct values from the range 0 to n, in linear time with constant extra space.

Problem Statement

Given an array nums holding n distinct numbers drawn from the range 0 to n, return the single number in that range that does not appear.

Sorting exposes the gap but costs more than linear time, and a lookup set costs linear space. The follow-up asks for both at once: linear time with only constant extra space.

Constraints

n == nums.length
$1 \le n \le 10^4$
$0 \le \mathrm{nums}[i] \le n$
All the numbers of nums are unique.

Examples

Example 1

Input: nums = [3, 0, 1]
Output: 2

With n = 3 the full range is 0 to 3, and 2 is the only value absent.

Example 2

Input: nums = [0, 1]
Output: 2

With n = 2 the full range is 0 to 2, and 2 is the only value absent.

Example 3

Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8

With n = 9 the full range is 0 to 9, and 8 is the only value absent.

Example 4

Input: nums = [1]
Output: 0

The one-element input must come from [0, 1]. Since 1 is present, the missing value is zero, which must not be confused with a failure sentinel.

Intuition

There are n + 1 possible values but only n distinct array entries, so exactly one value is absent. For [3, 0, 1], compare the full range [0, 1, 2, 3] with the input: only 2 has no partner. A set makes this comparison explicit. XOR compresses it into one accumulator because equal values cancel, regardless of their order in the array.

Approaches

Lookup Set

Solution Details

Reveal Lookup Set: intuition, complexity, and code

Intuition

Dropping every value into a set turns each membership test into constant time: the missing number is simply the first value in 0 to n absent from the set. It is the most direct translation of the question, paying linear storage for that directness.

Step-by-Step Logic

Read Example 1 nums = [3, 0, 1] and load the values into the set {3, 0, 1}.
Test candidate 0: it is in the set, so move on.
Test candidate 1: it is in the set, so move on.
Test candidate 2: it is absent from the set, so it is the missing number.
Return 2, the expected output.

Why It Works

The set contains exactly the input values. The candidate scan covers every allowed value from zero through n, returning only a value not present in that set. Distinctness and the input length guarantee that exactly one candidate is absent, so the first absent candidate is the answer. The defensive -1 return is unreachable for valid input.

Dry Run

Lookup Set: variable states at each step
Phase	Value / candidate	Set before	Set after / action
insert	3	{}	{3}
insert	0	{3}	{3, 0}
insert	1	{3, 0}	{3, 0, 1}
scan	0	{3, 0, 1}	present; continue
scan	1	{3, 0, 1}	present; continue
scan	2	{3, 0, 1}	absent; return 2

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Let n be the input length. Inserting n values and scanning at most n + 1 candidates takes O(n) expected time under expected constant-time hash-set operations. The set allocates O(n) entries (including boxed Integer values in Java); the returned scalar takes O(1) space. No sorting or input mutation occurs.

Code

Solution.java

1import java.util.HashSet;2import java.util.Set;3
4class Solution {5    public int missingNumber(int[] nums) {6        Set<Integer> seen = new HashSet<>();7        for (int num : nums) {8            seen.add(num);9        }10        // The missing value may be n, so include the upper endpoint.11        for (int i = 0; i <= nums.length; i++) {12            if (!seen.contains(i)) {13                return i;14            }15        }16        return -1;17    }18}

Hints

Hint 1

If nothing were missing, the array would hold exactly 0 to n in some order. What single value breaks that picture in [3, 0, 1]?

Hint 2

A set of the values answers every is-it-missing test instantly; what does that storage cost?

Hint 3

XOR each index together with its value into one accumulator seeded with n: pairs cancel and only the missing number survives.

Edge Cases

Missing 0, as in [1]: all nonzero values cancel, leaving the valid answer 0.
Missing n itself, as in [0, 1]: no index reaches it, but the seed n = 2 survives the folding.
Single-element arrays such as [1]: one fold still isolates the missing 0.

Common Mistakes and Interview Tips

Sorting first and scanning for the gap, which costs $O(n \log n)$ time instead of linear.
Seeding the accumulator with 0 instead of n, which drops the top of the range and answers 0 whenever n itself is missing.
Stopping at the set solution and missing the constant-space follow-up.
Interview tip: explain why indices provide the complete expected range only after seeding n. XOR does not detect invalid inputs with duplicates or multiple missing numbers.

Key Takeaway

When a complete range has exactly one hole, pairing each element against its expected partner with XOR exposes the hole with no storage.