163.Missing Ranges

Tags: [sort], [range], [implementation]

Com: {g}

Link: https://leetcode.com/problems/missing-ranges/\#/description

Given a sorted integer array wherethe range of elements are in the inclusive range [lower,upper], return its missing ranges.

For example, given[0, 1, 3, 50, 75],lower= 0 andupper= 99, return["2", "4->49", "51->74", "76->99"].

Solution:

class Solution(object):
    def findMissingRanges(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: List[str]
        """
        if not nums:
            missing_ranges = [[lower, upper]]
            return self.build_missing_ranges_str_arr(missing_ranges)

        missing_ranges = []
        if lower < nums[0]:
            missing_ranges.append([lower, nums[0] - 1])

        prev = 0
        curr = 1
        while curr < len(nums):
            if nums[prev] + 1 < nums[curr]:
                missing_ranges.append([nums[prev] + 1, nums[curr] - 1])

            prev = curr
            curr += 1

        if nums[-1] < upper:
            missing_ranges.append([nums[-1] + 1, upper])

        return self.build_missing_ranges_str_arr(missing_ranges)

    def build_missing_ranges_str_arr(self, missing_ranges):
        if not missing_ranges:
            return []

        result = []
        for r in missing_ranges:
            if r[0] == r[1]:
                result.append(str(r[0]))
            else:
                result.append('{}->{}'.format(r[0], r[1]))

        return result

Revelation:

• We first build a missing_ranges array, each range is two element array, we don't care about whether the lower bound is equal to the upper bound. And then we use the function build_missing_ranges_str_arr to manage and generate the final result.

Note:

• Time complexity = O(n), n is the number of elements in the given array.
• Complexity = O(n), n is the number of elements in the given array.