LeetCode 163. Missing Ranges

Description

https://leetcode.com/problems/missing-ranges/

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

Example 1:

Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: ["2","4->49","51->74","76->99"]
Explanation: The ranges are:
[2,2] --> "2"
[4,49] --> "4->49"
[51,74] --> "51->74"
[76,99] --> "76->99"

Example 2:

Input: nums = [], lower = 1, upper = 1
Output: ["1"]
Explanation: The only missing range is [1,1], which becomes "1".

Example 3:

Input: nums = [], lower = -3, upper = -1
Output: ["-3->-1"]
Explanation: The only missing range is [-3,-1], which becomes "-3->-1".

Example 4:

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.

Example 5:

Input: nums = [-1], lower = -2, upper = -1
Output: ["-2"]

Constraints:

• -109 <= lower <= upper <= 109
• 0 <= nums.length <= 100
• lower <= nums[i] <= upper
• All the values of nums are unique.

Explanation

Iterate the numbers and record the latest visited number. Check if there is a gap between the current number and the previous number, if yes, record that gap. In the end, also check if there is a gap between the largest number in the array and the upper value.

Python Solution

class Solution:
    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
        results = []
        
        if not nums:
            gap = self.helper(lower, upper)
            results.append(gap)
            
            return results
        
        prev = lower - 1
        
        for num in nums:
            if prev + 1 != num:                
                gap = self.helper(prev + 1, num - 1)
                results.append(gap)
            prev = num    
        
        if nums[-1] < upper:
            gap = self.helper(nums[-1] + 1, upper)
            results.append(gap)
                    
        return results
    
    def helper(self, left, right):
        if left == right:
            return str(left)
        
        return str(left) + "->" + str(right)
        

• Time complexity: ~N
• Space complexity: ~N