Skip to main content
CodePeetCodePeet
CodePeet 150

Missing Number

EASYProblemSolveExternal Links

Description

Given an array nums containing n distinct numbers chosen from the range [0, n], return the only number in that range which is missing from the array.

In other words, there are n + 1 possible values (0 through n), but the array holds only n of them. Exactly one value is absent — find and return it.

Examples

Example 1

Input: nums = [3, 0, 1]

Output: 2

Explanation: The array has 3 elements, so n = 3 and the full range is [0, 1, 2, 3]. The values 0, 1, and 3 are present, but 2 is missing.

Example 2

Input: nums = [0, 1]

Output: 2

Explanation: The array has 2 elements, so n = 2 and the full range is [0, 1, 2]. Both 0 and 1 are present, but 2 (which equals n itself) is missing.

Example 3

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

Output: 8

Explanation: The array has 9 elements, so n = 9 and the full range is [0, 1, 2, ..., 9]. Every number except 8 is present, so 8 is the missing number.

Constraints

  • n == nums.length
  • 1 ≤ n ≤ 10^4
  • 0 ≤ nums[i] ≤ n
  • All the numbers of nums are unique

Editorial

Brute Force

Intuition

The most straightforward way to find the missing number is to sort the array first. Once the array is sorted, the number at index i should be exactly i (since the values range from 0 to n). The first index where this property breaks tells us which number is missing.

Think of it like lining up numbered jerseys in order on a rack. If you place jerseys 0, 1, 3, 4 in order on hooks 0 through 4, hook number 2 will be empty — that's where the missing jersey belongs. If every hook matches its jersey number, then the missing one must be the last number, n.

Step-by-Step Explanation

Let's trace through with nums = [3, 0, 1]:

Step 1: n = 3 (array length). The full range is [0, 1, 2, 3].

Step 2: Sort the array: [3, 0, 1] → [0, 1, 3].

Step 3: Check index 0: nums[0] = 0. Is 0 == 0? YES — matches.

Step 4: Check index 1: nums[1] = 1. Is 1 == 1? YES — matches.

Step 5: Check index 2: nums[2] = 3. Is 3 == 2? NO — mismatch! The number 2 is missing.

Step 6: Return 2.

Sorting-Based Missing Number Detection — Watch how sorting the array lets us detect the missing number by checking if each index matches its value. The first mismatch reveals the gap.

Algorithm

  1. Sort the array in ascending order.
  2. Traverse the sorted array from index 0 to n-1:
    • If nums[i] != i, return i — that is the missing number.
  3. If every index matches its value, the missing number must be n (the largest value in the range). Return n.

Code

#include <vector>
#include <algorithm>
using namespace std;

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:
    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
import java.util.Arrays;

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;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Sorting the array of n elements takes O(n log n). The subsequent linear scan is O(n). The sorting step dominates, giving O(n log n) overall.

Space Complexity: O(1) or O(n)

Depends on the sorting algorithm used. In-place sorts (like heapsort) use O(1) extra space. Python's Timsort and Java's Arrays.sort use O(n) auxiliary space in the worst case.

Why This Approach Is Not Efficient

The sorting approach runs in O(n log n) time. While this is acceptable for the given constraints (n ≤ 10^4), sorting rearranges the entire array just to locate a single missing value. We are doing far more work than necessary.

The fundamental question is: can we determine which number is missing without rearranging the data at all? If we could check membership in O(1) time, a single scan of the range [0, n] would suffice, bringing the time down to O(n) at the cost of O(n) space for a hash set.

Better Approach - Hash Set Lookup

Intuition

Instead of sorting, we can store all the numbers from the array into a hash set. A hash set provides O(1) average-time membership checks. Then we simply iterate through every number from 0 to n and ask: is this number in the set? The first number that is not in the set is our answer.

Imagine a roll call in a classroom. Instead of lining everyone up by number (sorting), you write all present students' IDs on a whiteboard (hash set). Then you read the class roster from 0 to n — the first ID not on the whiteboard is the absent student.

Step-by-Step Explanation

Let's trace through with nums = [3, 0, 1]:

Step 1: n = 3. Full range is [0, 1, 2, 3].

Step 2: Build hash set from array: {0, 1, 3}.

Step 3: Check 0: is 0 in set? YES.

Step 4: Check 1: is 1 in set? YES.

Step 5: Check 2: is 2 in set? NO — 2 is missing!

Step 6: Return 2.

Hash Set Lookup — Scanning for the Missing Number — Watch how we build a set of all present numbers and then scan the range [0, n] to find the one number absent from the set.

Algorithm

  1. Insert all elements of nums into a hash set.
  2. Iterate through every number i from 0 to n:
    • If i is not in the hash set, return i — it is the missing number.
  3. Since exactly one number is missing, the loop will always find it.

Code

#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int n = nums.size();
        
        for (int i = 0; i <= n; i++) {
            if (numSet.find(i) == numSet.end()) {
                return i;
            }
        }
        
        return -1;
    }
};
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
        
        return -1
import java.util.HashSet;
import java.util.Set;

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;
    }
}

Complexity Analysis

Time Complexity: O(n)

Building the hash set from the array is O(n). Checking each number from 0 to n involves n+1 lookups, each taking O(1) average time. Total: O(n).

Space Complexity: O(n)

We store all n elements in the hash set. This uses O(n) extra space, which is the main drawback compared to constant-space approaches.

Why This Approach Is Not Efficient

The hash set approach achieves O(n) time, which is optimal for this problem. However, it requires O(n) extra space for the set. The follow-up challenge explicitly asks for O(1) space.

Can we avoid storing anything extra at all? The key insight comes from mathematics. We know the exact sum of all numbers from 0 to n: it is n × (n + 1) / 2. If we subtract the actual sum of the array from this expected sum, the difference must be the missing number. This uses pure arithmetic — no extra data structures — achieving O(n) time with O(1) space.

Optimal Approach - Sum Formula

Intuition

The sum of the first n natural numbers (0 through n) is given by the well-known formula: n × (n + 1) / 2. If no number were missing, the sum of all elements in the array would equal this value. Since exactly one number is absent, the difference between the expected sum and the actual sum reveals which number is gone.

Imagine a piggy bank that should contain coins numbered 0 to n. You know the total value should be n × (n + 1) / 2. You pour out the coins and count their total. Whatever amount is short — that's the number on the missing coin.

To avoid any potential overflow issues, instead of computing both sums separately, we can run a single loop: start with result = n, and for each index i, add i and subtract nums[i]. At the end, the accumulated difference is the missing number.

Step-by-Step Explanation

Let's trace through with nums = [3, 0, 1]:

Step 1: n = 3. Initialize result = n = 3.

Step 2: i = 0: result = result + 0 - nums[0] = 3 + 0 - 3 = 0.

Step 3: i = 1: result = result + 1 - nums[1] = 0 + 1 - 0 = 1.

Step 4: i = 2: result = result + 2 - nums[2] = 1 + 2 - 1 = 2.

Step 5: Loop complete. result = 2. Return 2.

Verification: expected sum = 3 × 4 / 2 = 6. Actual sum = 3 + 0 + 1 = 4. Missing = 6 - 4 = 2. ✓

Sum Formula — Running Difference Accumulation — Watch how we accumulate the difference between expected indices and actual array values. The running total converges to the missing number.

Algorithm

  1. Let n be the length of the array.
  2. Initialize result = n.
  3. For each index i from 0 to n-1:
    • Add i to result.
    • Subtract nums[i] from result.
  4. After the loop, result holds the missing number. Return it.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int result = n;
        
        for (int i = 0; i < n; i++) {
            result += i - nums[i];
        }
        
        return result;
    }
};
class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        n = len(nums)
        result = n
        
        for i in range(n):
            result += i - nums[i]
        
        return result
class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int result = n;
        
        for (int i = 0; i < n; i++) {
            result += i - nums[i];
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the array exactly once. Each iteration performs constant-time arithmetic (one addition and one subtraction). Total: O(n).

Space Complexity: O(1)

We use only a single integer variable (result) regardless of input size. No additional data structures are needed. This satisfies the follow-up requirement of O(1) extra space.