Problem 2.3 · ArraysEasy

Missing Number

PatternIndex as Hash (Cyclic Sort)Bit Manipulation

What it teaches: When values are 0..n, the index itself can act as the hash. Also the arithmetic shortcut, and how to avoid its overflow.

Practise it on judges as “Missing Number”.

The problem

nums contains n distinct numbers from the range [0, n], so exactly one number in that range is missing. Return it.

Example 1

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

Example 2

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

Example 3

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

Constraints

1 ≤ n ≤ 10⁴
0 ≤ nums[i] ≤ n
All numbers are distinct

Pattern clues in the wording

→ Values are exactly the range 0..n with one gap
→ The value tells you where it belongs
→ O(1) extra space is possible

These clues point to Index as Hash (Cyclic Sort): When values are in the range 1..n, put each value at its own index (or mark that index) to find missing or duplicate numbers in O(1) space.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int missingNumber(int[] nums) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

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

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Hash set · O(n)2. Index as hash (cyclic sort) · O(n)3. Shortcut: expected sum minus actual sum · O(n)

Hash set

Time O(n) Space O(n)

Put all values in a set, then check 0..n for the first one that's missing.

Approach 1

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) seen.add(x);
        for (int v = 0; v <= nums.length; v++) if (!seen.contains(v)) return v;
        return -1;
    }
}

Verdict: Works, but the range structure lets us do it without extra memory.

Index as hash (cyclic sort)

Time O(n) Space O(1)

Each value v in 0..n−1 belongs at index v. Swap values into their own index; the value n has no slot, so leave it. Afterwards, the first index i where nums[i] != i is the missing number. If every index matches, the missing number is n.

▶ Dry run: Sending each value homenums = [3, 0, 1]

↑i

Step 1/63 belongs at index 3, which doesn't exist (n = 3). Leave it and move on.

Approach 2

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length, i = 0;
        while (i < n) {
            int v = nums[i];
            if (v < n && v != nums[v]) {      // v has a home slot and isn't there yet
                nums[i] = nums[v];
                nums[v] = v;
            } else {
                i++;
            }
        }
        for (i = 0; i < n; i++) if (nums[i] != i) return i;
        return n;
    }
}

Verdict: No extra memory. The same idea solves harder problems like First Missing Positive.

Shortcut: expected sum minus actual sum

Time O(n) Space O(1)

0 + 1 + ... + n = n(n + 1) / 2. Subtract every element; what's left is the missing number. For large n the sum can overflow an int, so either use long or subtract as you go (missing += i + 1 - nums[i]), which keeps the running value small. XOR works the same way without overflow: XOR all indexes 0..n and all values, and pairs cancel.

Approach 3

class Solution {
    public int missingNumber(int[] nums) {
        int missing = 0;
        for (int i = 0; i < nums.length; i++) {
            missing += (i + 1) - nums[i];    // never grows beyond n, no overflow
        }
        return missing;
    }
}

Verdict: The shortest answer. Mention the overflow issue to show care.

Before you submit

Edge cases and common mistakes

Test these inputs

Missing 0
Missing n (all indexes match)
n = 1

Mistakes people make

Computing n(n+1)/2 in an int for large n (overflow).
In cyclic sort, advancing i after every swap: the value swapped in may also need moving.
Forgetting that the value n has no slot and looping forever trying to place it.

Interview

Follow-up questions

How does the XOR version work?

What if two numbers are missing?

Command Palette