Description
https://leetcode.com/problems/missing-ranges/
Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], 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”