268. Missing Number - Explanation

Description

Given an array nums containing n integers in the range [0, n] without any duplicates, return the single number in the range that is missing from nums.

Follow-up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Example 1:

Input: nums = [1,2,3]

Output: 0

Explanation: Since there are 3 numbers, the range is [0,3]. The missing number is 0 since it does not appear in nums.

Example 2:

Input: nums = [0,2]

Output: 1

Constraints:

1 <= nums.length <= 1000

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Hint 1

A brute force approach would iterate through the range of numbers from 0 to n, checking if each number is present in the given array. If a number is missing, it is returned. This results in an O(n^2) solution. Can you think of a better way? Maybe a data structure could help optimize this process.

Hint 2

We can use a hash set by inserting the given array elements into it. Then, we iterate through the range of numbers from 0 to n and use the hash set for O(1) lookups to find the missing number. Can you think of a way to further optimize this? Maybe a bitwise operator could be useful.

Hint 3

We can use bitwise XOR. When two identical numbers are XORed, the result is 0. Using this property, we can efficiently find the missing number.

Hint 4

We first compute the bitwise XOR of numbers from 0 to n. Then, we iterate through the array and XOR its elements as well. The missing number remains in the final XOR result since all other numbers appear twice—once in the range and once in the array—while the missing number is XORed only once.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Bitwise XOR - The XOR approach uses the property that a number XORed with itself equals zero to cancel out all present numbers
Math (Sum Formula) - The mathematical approach uses the sum formula for consecutive integers to find the missing value
Hash Set - One solution uses constant-time lookups to identify which number from the expected range is absent

1. Sorting

Intuition

We are given an array containing n distinct numbers taken from the range [0, n].
Exactly one number is missing, and we need to find it.

A simple way to reason about this is:

If the array were complete and sorted, the number at index i should be exactly i
As soon as this condition breaks, that index represents the missing number

Sorting the array puts the numbers in order, making this comparison straightforward and beginner-friendly.

Algorithm

Sort the array in ascending order.
Traverse the array from index 0 to n - 1:
- If nums[i] != i, then i is the missing number → return i.
If all indices match their values:
- The missing number must be n → return n as the result.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        for i in range(n):
            if nums[i] != i:
                return i
        return n

public class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return n;
    }
}

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return n;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    missingNumber(nums) {
        let n = nums.length;
        nums.sort((a, b) => a - b);
        for (let i = 0; i < n; i++) {
            if (nums[i] !== i) {
                return i;
            }
        }
        return n;
    }
}

public class Solution {
    public int MissingNumber(int[] nums) {
        int n = nums.Length;
        Array.Sort(nums);
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return n;
    }
}

class Solution {
    fun missingNumber(nums: IntArray): Int {
        val n = nums.size
        nums.sort()
        for (i in 0 until n) {
            if (nums[i] != i) {
                return i
            }
        }
        return n
    }
}

class Solution {
    func missingNumber(_ nums: [Int]) -> Int {
        var nums = nums.sorted()
        let n = nums.count
        for i in 0..<n {
            if nums[i] != i {
                return i
            }
        }
        return n
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

2. Hash Set

Intuition

We are given n distinct numbers taken from the range [0, n], with exactly one number missing.

A natural way to approach this is to ask:

“Can we quickly check whether a number exists in the array?”

Using a hash-based data structure (like a hash set) allows us to:

Store all given numbers
Check the presence of any number in constant time

Once all numbers are stored, we simply look for the number in the range [0, n] that does not appear in the set.

This approach trades a little extra space for very clear and simple logic.

Algorithm

Insert all elements of the array into a hash set.
Iterate through all numbers from 0 to n:
- If a number is not present in the set, return it as the missing number.
Since exactly one number is missing, this process will always find the answer.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        num_set = set(nums)
        n = len(nums)
        for i in range(n + 1):
            if i not in num_set:
                return i

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

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        unordered_set<int> num_set(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 0; i <= n; i++) {
            if (num_set.find(i) == num_set.end()) {
                return i;
            }
        }
        return -1;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    missingNumber(nums) {
        const numSet = new Set(nums);
        const n = nums.length;
        for (let i = 0; i <= n; i++) {
            if (!numSet.has(i)) {
                return i;
            }
        }
    }
}

public class Solution {
    public int MissingNumber(int[] nums) {
        HashSet<int> numSet = new HashSet<int>(nums);
        int n = nums.Length;
        for (int i = 0; i <= n; i++) {
            if (!numSet.Contains(i)) {
                return i;
            }
        }
        return -1;
    }
}

func missingNumber(nums []int) int {
    numSet := make(map[int]struct{})
    for _, num := range nums {
        numSet[num] = struct{}{}
    }
    n := len(nums)
    for i := 0; i <= n; i++ {
        if _, exists := numSet[i]; !exists {
            return i
        }
    }
    return -1
}

class Solution {
    fun missingNumber(nums: IntArray): Int {
        val numSet = nums.toSet()
        val n = nums.size
        for (i in 0..n) {
            if (i !in numSet) {
                return i
            }
        }
        return -1
    }
}

class Solution {
    func missingNumber(_ nums: [Int]) -> Int {
        let numSet = Set(nums)
        let n = nums.count
        for i in 0...n {
            if !numSet.contains(i) {
                return i
            }
        }
        return -1
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Bitwise XOR

Intuition

We are given n distinct numbers from the range [0, n], with exactly one number missing.

A very powerful observation comes from the properties of XOR (⊕):

a ⊕ a = 0 (a number cancels itself)
a ⊕ 0 = a
XOR is commutative and associative (order does not matter)

If we XOR:

all numbers from 0 to n
and all numbers present in the array

Every number that appears in both places will cancel out, leaving only the missing number.

This allows us to find the answer in linear time and constant space, without sorting or extra data structures.

Algorithm

Let n be the length of the array.
Initialize a variable xorr with n.
For each index i from 0 to n - 1:
- XOR xorr with i
- XOR xorr with nums[i]
After the loop, xorr will contain the missing number.
Return xorr.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        xorr = n
        for i in range(n):
            xorr ^= i ^ nums[i]
        return xorr

public class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int xorr = n;
        for (int i = 0; i < n; i++) {
            xorr ^= i ^ nums[i];
        }
        return xorr;
    }
}

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int xorr = n;
        for (int i = 0; i < n; i++) {
            xorr ^= i ^ nums[i];
        }
        return xorr;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    missingNumber(nums) {
        let n = nums.length;
        let xorr = n;
        for (let i = 0; i < n; i++) {
            xorr ^= i ^ nums[i];
        }
        return xorr;
    }
}

public class Solution {
    public int MissingNumber(int[] nums) {
        int n = nums.Length;
        int xorr = n;
        for (int i = 0; i < n; i++) {
            xorr ^= i ^ nums[i];
        }
        return xorr;
    }
}

class Solution {
    fun missingNumber(nums: IntArray): Int {
        val n = nums.size
        var xorr = n
        for (i in 0 until n) {
            xorr = xorr xor i xor nums[i]
        }
        return xorr
    }
}

class Solution {
    func missingNumber(_ nums: [Int]) -> Int {
        let n = nums.count
        var xorr = n

        for i in 0..<n {
            xorr ^= i ^ nums[i]
        }

        return xorr
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

4. Math

Intuition

We are given n distinct numbers from the range [0, n], with exactly one number missing.

A simple mathematical observation helps here:

The sum of numbers from 0 to n is known
If we subtract the sum of the given array from this expected sum, the result must be the missing number

Instead of computing two separate sums, we can combine both ideas into a single running calculation, which keeps the logic clean and avoids overflow issues in some languages.

This approach uses basic arithmetic, making it easy to understand and language-independent.

Algorithm

Let n be the length of the array.
Initialize a variable res = n.
For each index i from 0 to n - 1:
- Add i to res
- Subtract nums[i] from res
After the loop, res will hold the missing number.
Return res as the answer.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        res = len(nums)

        for i in range(len(nums)):
            res += i - nums[i]
        return res

public class Solution {
    public int missingNumber(int[] nums) {
        int res = nums.length;

        for (int i = 0; i < nums.length; i++) {
            res += i - nums[i];
        }
        return res;
    }
}

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = nums.size();

        for (int i = 0; i < nums.size(); i++) {
            res += i - nums[i];
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    missingNumber(nums) {
        let res = nums.length;

        for (let i = 0; i < nums.length; i++) {
            res += i - nums[i];
        }
        return res;
    }
}

public class Solution {
    public int MissingNumber(int[] nums) {
        int res = nums.Length;

        for (int i = 0; i < nums.Length; i++) {
            res += i - nums[i];
        }
        return res;
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Forgetting That n Could Be the Missing Number

The range is [0, n] for an array of length n, meaning n itself could be missing. Solutions that only check indices 0 to n-1 will miss this case and fail to return n when all other numbers are present.

Integer Overflow in Sum-Based Approach

When using the mathematical approach, computing the full expected sum n * (n + 1) / 2 separately before subtracting can cause overflow for large n. Combining addition and subtraction in a single loop avoids this issue.