Description:
You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in the inclusive range.
A number x is considered missing if x is in the range [lower, upper] and x is not in nums.
Return the smallest sorted list of ranges that cover every missing number exactly. That is, no element of nums is in any of the ranges, and each missing number is in one of the ranges.
Each range [a,b] in the list should be output as:
"a->b" if a != b
"a" if a == b
Solution:
Time Complexity : O(n)
Space Complexity: O(1)
var findMissingRanges = function(nums, lower, upper) {
// array to add ranges
const result = []
// start at lower - 1 for edge case where lower === nums[0]
let prev = lower - 1;
// loop for nums.length times so we can compare the last value with upper
for (let i = 0; i <= nums.length; i++) {
// current number to compare to prev
// when i === nums.length we will compare prev = nums[nums.length-1] and upper
// the upper+1 is to account for nums[nums.length-1]===upper
let curr = (i < nums.length) ? nums[i] : upper + 1;
// check if we need to add a range to the array
if (prev + 1 <= curr - 1) {
// if equal then add any of the numbers to the array
// if < than, then add the range string to the array
result.push(prev + 1===curr - 1?`${prev + 1}`:`${prev + 1}->${curr - 1}`);
}
// set prev to compare in the next iteration
prev = curr;
}
return result
};
Top comments (0)