You are given an integer array nums consisting of unique integers.
Originally, nums contained every integer within a certain range. However, some integers might have gone missing from the array.
The smallest and largest integers of the original range are still present in nums.
Return a sorted list of all the missing integers in this range. If no integers are missing, return an empty list.
Example 1:
Input: nums = [1,4,2,5]
Output: [3]
Explanation:
The smallest integer is 1 and the largest is 5, so the full range should be [1,2,3,4,5]. Among these, only 3 is missing.
Example 2:
Input: nums = [7,8,6,9]
Output: []
Explanation:
The smallest integer is 6 and the largest is 9, so the full range is [6,7,8,9]. All integers are already present, so no integer is missing.
Example 3:
Input: nums = [5,1]
Output: [2,3,4]
Explanation:
The smallest integer is 1 and the largest is 5, so the full range should be [1,2,3,4,5]. The missing integers are 2, 3, and 4.
Constraints:
2 <= nums.length <= 100
1 <= nums[i] <= 100
My Solution
We can solve this problem by iterating through the array once to capture the maximum and minimum values. We also add all numbers to a HashSet for fast access. Then we iterate from min to max and if the number is not in the HashSet we add that number to our output list.
Time complexity is O(max-min) because we iterate through the range to find the missing numbers. max-min in this problem will always be greater than or equal to the length of the array.
class Solution {
public List<Integer> findMissingElements(int[] nums) {
int min = Integer.MAX_VALUE;
int max = 0;
List<Integer> out = new ArrayList<>();
int n = nums.length;
Set<Integer> distinct = new HashSet<>();
for (int num : nums) {
min = Math.min(min, num);
max = Math.max(max, num);
distinct.add(num);
}
for (int i = min; i <= max; i++) {
if (!distinct.contains(i)) {
out.add(i);
}
}
return out;
}
}