Missing Ranges

Description

Given a sorted integer array where the range of elements are in the inclusive range [lower, upper], return its missing ranges.

Example

Example 1

Input:
nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99
Output:
["2", "4->49", "51->74", "76->99"]
Explanation:
in range[0,99],the missing range includes:range[2,2],range[4,49],range[51,74] and range[76,99]

Example 2

Input:
nums = [0, 1, 2, 3, 7], lower = 0 and upper = 7
Output:
["4->6"]
Explanation:
in range[0,7],the missing range include range[4,6]

Solution

Approach1:

We iterate through the entire array. We update the lower to the next number of current element, after it’s been processed. We check whether lower is less than the current element -1 , that means , this is the range to be added to the result. If the lower and current element-1 is found to be same , then there is a single number to be added to the result. These 2 conditions are made using an if - else statement. Also one thing note is , that the given array is expanded by adding a term upper+1 to the array, so that, every possible ranges are added to the result using a loop, rather than a seperate conditional check for the upper bound.

def findMissingRanges(self, nums, lower, upper):
     arr=[] 
     nums+=[upper+1]
     n=len(nums)
     for i in range(n):
        if(lower<nums[i]-1):
            arr.append(str(lower)+"->"+str(nums[i]-1))
        elif(lower==nums[i]-1):
            arr.append(str(lower))
        lower=nums[i]+1
     return arr

Time:O(n)

Space:O(1)