Missing Number
EASYDescription
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
Checkout 5 different approaches to solve Missing Number. Click on different approaches to view the approach and algorithm in detail.
Sorting Based Approach
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
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 Analysis
Pros and Cons
- Easy to understand
- No extra space needed (if using in-place sorting)
- Works well for small arrays
- Modifies the original array
- Not as efficient as other solutions
- Sorting is expensive
Code Solutions
Checking out 4 solutions in different languages for Missing Number. Click on different languages to view the code.
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 Solution
Watch the video walkthrough for Missing Number
Similar Questions
5 related questions you might find useful
Algorithms:
Patterns:
Data Structures:
Companies:
Subscribe to Scale Engineer newsletter
Learn about System Design, Software Engineering, and interview experiences every week.
No spam, unsubscribe at any time.