Python solution with detailed explanation

  • 0


    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:
            elif s < e: # Important
                result.append(str(s) + "->" + str(e))
        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
                    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.