Missing Number
EasyPrompt
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:
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:
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 in the range since it does not appear in nums.
Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation:
n = 9 since there are 9 numbers, 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.length1 <= n <= 1040 <= nums[i] <= n- All the numbers of
numsare unique.
Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
Approaches
5 approaches with complexity analysis and trade-offs.
Sort the array first and then check for the first missing number by comparing adjacent elements.
Algorithm
- Sort the array in ascending order
- If first element is not 0, return 0
- If last element is not n, return n
- Iterate through sorted array checking for gaps between consecutive numbers
- Return the first gap found
Walkthrough
First, we sort the array in ascending order. Then we iterate through the sorted array and check if each number is equal to its index. The first position where this condition fails is our missing number. If we reach the end without finding a mismatch, then n is the missing number.
public int missingNumber(int[] nums) { Arrays.sort(nums); int n = nums.length; // Check if n is missing if (nums[n-1] != n) { return n; } // Check if 0 is missing if (nums[0] != 0) { return 0; } for (int i = 1; i < n; i++) { int expectedNum = nums[i-1] + 1; if (nums[i] != expectedNum) { return expectedNum; } } return -1;}Complexity
Time
O(n log n) - Dominated by the sorting operation
Space
O(1) - Only using constant extra space
Trade-offs
Pros
Easy to understand
No extra space needed (if using in-place sorting)
Works well for small arrays
Cons
Modifies the original array
Not as efficient as other solutions
Sorting is expensive
Use a HashSet to store all numbers from the array, then find the missing number by checking which number from 0 to n is not in the set.
Algorithm
- Create a HashSet
- Add all numbers from array to HashSet
- Check each number from 0 to n
- Return first number not found in HashSet
Walkthrough
We first create a HashSet and add all numbers from the array to it. Then we iterate from 0 to n and check which number is not present in the set. That number is our missing number.
public int missingNumber(int[] nums) { Set<Integer> set = new HashSet<>(); int n = nums.length; // Add all numbers to set for (int num : nums) { set.add(num); } // Find missing number for (int i = 0; i <= n; i++) { if (!set.contains(i)) { return i; } } return -1;}Complexity
Time
O(n) - We traverse the array once to build the set and once to find the missing number
Space
O(n) - We store all numbers in a HashSet
Trade-offs
Pros
O(n) time complexity
Easy to implement
Does not modify original array
Cons
Requires extra space
Not as space efficient as other solutions
Use the formula for sum of first n natural numbers and subtract the sum of array elements to find the missing number.
Algorithm
- Calculate expected sum using formula: n*(n+1)/2
- Calculate actual sum of array elements
- Return the difference between expected and actual sum
Walkthrough
We can find the missing number by calculating the difference between the expected sum of numbers from 0 to n and the actual sum of numbers in the array. The expected sum can be calculated using the formula n*(n+1)/2.
public int missingNumber(int[] nums) { int n = nums.length; int expectedSum = (n * (n + 1)) / 2; int actualSum = 0; for (int num : nums) { actualSum += num; } return expectedSum - actualSum;}Complexity
Time
O(n) - We only need to traverse the array once to calculate the sum
Space
O(1) - Only using constant extra space
Trade-offs
Pros
O(n) time complexity
O(1) space complexity
Simple and elegant solution
Does not modify original array
Cons
Might have integer overflow for large values
Not as intuitive as other approaches
Use XOR operation to find the missing number by exploiting the properties of XOR operation.
Algorithm
- Initialize result with n
- XOR result with each index and value in array
- Return result which will be the missing number
Walkthrough
We can use XOR operation to find the missing number. XOR all numbers from 0 to n with all numbers in the array. Due to XOR properties (a^a=0 and a^0=a), all numbers except the missing one will be cancelled out.
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
Time
O(n) - We only need to traverse the array once
Space
O(1) - Only using constant extra space
Trade-offs
Pros
O(n) time complexity
O(1) space complexity
No risk of integer overflow
Most efficient solution
Does not modify original array
Cons
Not as intuitive as other approaches
Requires understanding of XOR properties
Check each number from 0 to n if it exists in the array. The first number that is not found in the array is the missing number.
Algorithm
- For each number i from 0 to n:
- Search for i in the array nums
- If i is not found, return i
Walkthrough
This approach involves iterating through each number from 0 to n and for each number, we search the entire array to check if it exists. If a number is not found in the array, that is our missing number.
public int missingNumber(int[] nums) { int n = nums.length; for (int i = 0; i <= n; i++) { boolean found = false; for (int j = 0; j < n; j++) { if (nums[j] == i) { found = true; break; } } if (!found) { return i; } } return -1;}Complexity
Time
O(n²) - For each number from 0 to n, we search the entire array
Space
O(1) - Only using constant extra space
Trade-offs
Pros
Simple to understand and implement
No extra space required
Cons
Very inefficient for large arrays
Requires nested loops
Solutions
Solution
class Solution {public int missingNumber(int[] nums) { int n = nums.length; int ans = n; for (int i = 0; i < n; ++i) { ans ^= (i ^ nums[i]); } return ans; }}/** * @param {number[]} nums * @return {number} */ var missingNumber = function (nums) { const n = nums.length; let ans = n; for (let i = 0; i < n; ++i) { ans ^= i ^ nums[i]; } return ans; };class Solution {public: int missingNumber(vector<int> &nums) { int n = nums.size(); int ans = n; for (int i = 0; i < n; ++i) { ans ^= (i ^ nums[i]); } return ans; }};class Solution: def missingNumber( self, nums: List[int]) -> int: return reduce(xor, (i ^ v for i, v in enumerate(nums, 1)))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.