DEV Community

codingpineapple
codingpineapple

Posted on

Leetcode 163. Missing Ranges (javascript solution)

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 
};
Enter fullscreen mode Exit fullscreen mode

Discussion (0)