Missing Number

EasyCyclic SortBlind 75JuniorOpen on LeetCodeUpdated Sep 21, 2026

You're given an array nums of n distinct integers, each between 0 and n inclusive, in no particular order. That range holds n + 1 values, so exactly one of them is absent from nums. Return the missing value; note that it can be n itself. Aim for O(n) time and O(1) extra space.

Examples

nums = [3,0,1] returns 2

n = 3, so the range is 0, 1, 2 and 3. 0, 1 and 3 are present, which leaves 2.

nums = [0,1] returns 2

n = 2, so the range is 0 to 2. Both 0 and 1 are there, so the missing value is n itself, 2.

Constraints

1 <= n <= 10^4
All numbers are distinct and in [0, n].

Hints

Hint 1

Values come from 0..n with no duplicates, what if each value belonged at a specific index?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Every value v < n has a home, index v. Walk the array: while nums[i] is less than n and not at its home, swap it into index nums[i]; otherwise move on. Each swap parks one value for good, so there are at most n swaps. Then the first index j with nums[j] != j is the missing number, and if every index matches, the answer is n. It rearranges nums in place.

Time

O(n)

Space

O(1)

Pitfall

The value n has no home index (index n is past the end), so leave it where it is instead of swapping, or you'll go out of bounds. If every index holds its own value after the pass, the missing number is n.

Solutions

class Solution {
    public int missingNumber(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            if (nums[i] < nums.length && nums[i] != i) {
                int tmp = nums[i];
                nums[i] = nums[tmp];
                nums[tmp] = tmp;
            } else {
                i++;
            }
        }
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] != j) return j;
        }
        return nums.length;
    }
}

class Solution:
    def missingNumber(self, nums):
        i, n = 0, len(nums)
        while i < n:
            if nums[i] < n and nums[i] != i:
                j = nums[i]
                nums[i], nums[j] = nums[j], nums[i]
            else:
                i += 1
        for j in range(n):
            if nums[j] != j:
                return j
        return n