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.length
- 1 <= n <= 104
- 0 <= nums[i] <= n
- All the numbers of nums are unique.
My Solution
We can solve this problem by marking the numbers as we encounter them by making the corresponding indices negative. Then we iterate through the array again and if we encounter a positive number, we return that index, since we know that we didn’t see the corresponding number. If we go through the whole array without seeing a positive number, we know that we have to return n. There are a few details to take care of. We do a pass through the array where we increment every number by one. This takes care of the case where multiplying -1 by 0 would not make the number at that index negative. Then because we incremented all the numbers by one, we find the index corresponding to the number by subtracting 1 from it’s absolute value.
Time complexity is O(n) because we do 3 passes through the array. Space complexity is O(1) because we only require constant extra space.
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
nums[i]++;
}
for (int i = 0; i < n; i++) {
int idx = Math.abs(nums[i]) - 1;
if (idx < n) {
nums[idx] *= -1;
}
}
for (int i = 0; i < n; i++) {
if (nums[i] > 0) {
return i;
}
}
return n;
}
}