Python solution with detailed explanation


  • 0
    G

    Solution

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

    Optimized method

    • Visualize the summary on the number line. Then visualize lower and upper wrapped around it.
    • Use a variable called next_expected and initialize to lower.
    • Iterate through nums. If x is same as next_expected, increment next_expected by 1. Otherwise you have discovered a missing range as next_expected to x-1. The new next_expected will be x + 1.
    • Be careful about the final range involving upper.
    • Also notice that add_range method and the use of s < e.
    class Solution(object):
        def add_range(self, nums, s, e, result):
            if s == e:
                result.append(str(s))
            elif s < e: # Important
                result.append(str(s) + "->" + str(e))
            return
        
        def findMissingRanges(self, nums, lower, upper):
            """
            :type nums: List[int]
            :type lower: int
            :type upper: int
            :rtype: List[str]
            """
            result = []
            next_expected = lower
            for x in nums:
                if x == next_expected:
                    next_expected = next_expected + 1 # Important
                    continue
                else:
                    s,e = next_expected, x-1
                    self.add_range(nums, s, e, result)
                    next_expected = x + 1
            self.add_range(nums, next_expected, upper, result)
            return result        
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.