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