# 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)