LeetCode 163. Missing Ranges

Description

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

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

Example:

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

Explanation

whenever find a gap between numbers, create a missing range

Python Solution

class Solution:
    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
        results = []
        
        if not nums:
            results.append(self.format_helper(lower, upper))
            return results
        
        prev_num = lower - 1
        for num in nums:
            if prev_num != num and num - 1 != prev_num:                
                missing = self.format_helper(prev_num + 1, num - 1)                
                results.append(missing)
                prev_num = num                
            else:
                prev_num = num
                
        if nums[-1] != upper:
            missing = self.format_helper(nums[-1] + 1, upper)
            results.append(missing)
        
        
        return results
    
    def format_helper(self, left, right):
        if left == right:
            return str(left)
        else:
            return str(left) + "->" + str(right)
  • Time complexity: ~N
  • Space complexity: ~N

2 Thoughts to “LeetCode 163. Missing Ranges”

Leave a Reply

Your email address will not be published. Required fields are marked *