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)