Log inSign up
easyLeetCodeNot Started

Missing Number

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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

Example 1 · Standard 3-element Array:

Input: nums = [3, 0, 1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0, 3]. 2 is the missing number in the range since it does not appear in nums.

Example 2 · 2-element Array with Missing 2:

Input: nums = [0, 1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0, 2]. 2 is the missing number since it does not appear in nums.

Example 3 · 9-element Array with Missing 8:

Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8
Explanation: n = 9, so all numbers are in the range [0, 9]. 8 is the missing number in the range since it does not appear in nums.

Constraints:

  • n == nums.length
  • 1 <= n <= 104
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Sum of arithmetic series (1 + 2 + ... + n = n*(n+1)/2)
  • Bitwise XOR properties (a ^ a = 0 and a ^ 0 = a)
  • Linear array traversal

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply Gauss's formula n * (n + 1) / 2 to compute sequence totals in O(1) time.
  • Master the XOR bitwise cancellation trick to avoid integer overflow.
  • Evaluate trade-offs between sorting (O(N log N)), hash sets (O(N) space), and bit manipulation (O(1) space).
  • Write concise, production-ready code across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Array contains N distinct numbers from the continuous range [0, N].
  • Exactly one number is missing from the full arithmetic sequence.
  • Requires O(N) time and O(1) auxiliary space.

Algorithmic Decision Tree:

  • If values are within 32-bit integer limits: Use Gauss Sum Formula expectedSum - actualSum for instantaneous O(N) time and O(1) space.
  • If integer overflow is a concern: Use XOR bitwise reduction across 0..N and nums[i].

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Brute Force — Sort & Compare Indices

Intuition

Sort the array in ascending order and check if each element matches its index. If nums[i] != i, then i is the missing number.

Algorithm

  1. Sort nums in ascending order.
  2. Loop i from 0 to n - 1:
  3. If nums[i] != i, return i.
  4. If loop completes without returning, return n.

Brute force — search for each expected value

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
The first expected value is present
Visual state
Values and pointers at this exact step
array
S
3
0
1
0
1
2
Variables at this step
expected
0
found
true
Check / comparison
Expected values are 0, 1, and 2.
Decision / next transition
Search the array for 0.
Why this step matters

The first expected value is present.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <algorithm>
2#include <iostream>
3#include <vector>
4using namespace std;
5
6// Brute Force: Sort and match indices
7int missingNumber(vector<int>& nums) {
8 sort(nums.begin(), nums.end());
9 int n = nums.size();
10
11 for (int i = 0; i < n; i++) {
12 if (nums[i] != i) {
13 return i;
14 }
15 }
16 return n;
17}
18
19int main() {
20 vector<int> nums = {3, 0, 1};
21 cout << "Output: " << missingNumber(nums) << endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Approach 1: Brute Force — Sort & Compare Indices.
  • Space complexity: O(1) — Space complexity for Approach 1: Brute Force — Sort & Compare Indices.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Better — Hash Set Lookup

Intuition

Insert all elements into a Hash Set, then check each integer from 0 to n for presence in O(1) average time.

Algorithm

  1. Insert all numbers in nums into a hash set numSet.
  2. Loop i from 0 to n:
  3. If i is not in numSet, return i.
  4. Return -1.

Better — sort and inspect expected positions

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Sorting makes each value's expected index easy to compare
Visual state
Values and pointers at this exact step
array
S
3
0
1
0
1
2
Variables at this step
before
[3,0,1]
Check / comparison
The array is not sorted.
Decision / next transition
Sort the values.
Why this step matters

Sorting makes each value's expected index easy to compare.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_set>
3#include <vector>
4using namespace std;
5
6// Better: Hash Set lookup in O(N) time and O(N) space
7int missingNumber(vector<int>& nums) {
8 unordered_set<int> numSet(nums.begin(), nums.end());
9 int n = nums.size();
10
11 for (int i = 0; i <= n; i++) {
12 if (numSet.find(i) == numSet.end()) {
13 return i;
14 }
15 }
16 return -1;
17}
18
19int main() {
20 vector<int> nums = {3, 0, 1};
21 cout << "Output: " << missingNumber(nums) << endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Approach 2: Better — Hash Set Lookup.
  • Space complexity: O(N) — Space complexity for Approach 2: Better — Hash Set Lookup.

3. Optimal — Gauss Math Sum & XOR (O(1) Space)

Intuition

Compute expected sum n * (n + 1) / 2 and subtract the array sum, or XOR all numbers from 0..n with nums[i] to cancel duplicates.

Algorithm

  1. Let n = nums.length.
  2. Calculate expectedSum = n * (n + 1) / 2.
  3. Calculate actualSum by summing all elements of nums.
  4. Return expectedSum - actualSum.

Optimal — XOR indices and values

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
XOR of indices 0 through n and all array values leaves only the missing value
Visual state
Values and pointers at this exact step
array
S
3
0
1
0
1
2
Variables at this step
xor
3
Check / comparison
Initialize xor with n=3.
Decision / next transition
Set xor = 3.
Why this step matters

XOR of indices 0 through n and all array values leaves only the missing value.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4using namespace std;
5
6// Optimal: Gauss Sum Formula (O(N) time, O(1) space)
7int missingNumber(vector<int>& nums) {
8 long long n = nums.size();
9 long long expectedSum = n * (n + 1) / 2;
10 long long actualSum = 0;
11
12 for (int num : nums) {
13 actualSum += num;
14 }
15
16 return expectedSum - actualSum;
17}
18
19// Alternative XOR Solution:
20// int missingNumberXOR(vector<int>& nums) {
21// int xorVal = nums.size();
22// for (int i = 0; i < nums.size(); i++) {
23// xorVal ^= i ^ nums[i];
24// }
25// return xorVal;
26// }
27
28int main() {
29 vector<int> nums = {3, 0, 1};
30 cout << "Output: " << missingNumber(nums) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Approach 3: Optimal — Gauss Math Sum & XOR (O(1) Space).
  • Space complexity: O(1) — Space complexity for Approach 3: Optimal — Gauss Math Sum & XOR (O(1) Space).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Sort & MatchO(N log N)O(1) auxiliaryVery intuitive, checks index equality directly.Baseline only.
2.Hash Set LookupO(N)O(N)Linear time, easy to reason about.Good stepping stone; interviewer will ask to remove extra space.
3.Gauss Sum / XOR BitwiseOptimalO(N)O(1)Optimal linear time, strictly O(1) space, no extra allocations.Optimal gold standard.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Missing Number is 0 — Input: nums = [1, 2, 3], Expected: 0 — Ensure the algorithm correctly returns 0 when all elements 1..N are present.
  • Missing Number is N (the largest number) — Input: nums = [0, 1, 2], Expected: 3 — When all elements from 0 to N - 1 are present, the missing number is N.
  • Single Element Array (n = 1) — Input: nums = [0], Expected: 1 — With n = 1, range is [0, 1]. Since 0 is present, 1 is missing.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Demonstrating Breadth — Mention both the Gauss Sum formula and the XOR bitwise solution: 'Gauss sum is simplest, but XOR is especially attractive because it guarantees zero arithmetic overflow.'
  2. Complexity Clarification — Clearly state: 'Both Gauss and XOR operate in O(N) single-pass time with strictly O(1) auxiliary space.'
  3. Follow-up Question — Be ready for follow-up: 'What if two numbers are missing?' (Find sum and product, or use XOR partition based on rightmost set bit — Find Two Missing Numbers).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Missing Number?

2.Why is the brute force approach suboptimal for large inputs in Missing Number?

3.Which data structure or technique enables the optimal solution for Missing Number?

Back to DSA Sheet