163. Missing Ranges
- Total Accepted: 19465
- Total Submissions: 66232
- Difficulty: Medium
- Contributors: Admin
Given a sorted integer array where the range of elements are in the inclusive range [lower, upper], return its missing ranges.
For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].
Code
class Solution(object):
def findMissingRanges(self, nums, lower, upper):
"""
:type nums: List[int]
:type lower: int
:type upper: int
:rtype: List[str]
"""
if nums is None:
nums = []
res = []
nums = [lower-1] + nums + [upper+1]
for i in xrange(1, len(nums)):
prev, cur = nums[i-1], nums[i]
if cur - prev == 2:
res.append(str(cur-1))
elif cur - prev > 2:
res.append(str(prev+1) + '->' + str(cur-1))
return res
Idea
To make the code consistent in different cases, I add lower-1 in front of nums and append upper+1 in the end of nums. Then if the current element is exactlye greater than the previous element by 2, then we miss a single number; else, if the current element is greater than the previous element more than 2, then we miss a range; if the current element is just 1 greater than the previous element, we do not do anything.
Also see a similar question: https//nb4799.neu.edu/wordpress/?p=944