# LeetCode 163. Missing Ranges

## Description

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

You are given an inclusive range `[lower, upper]` and a sorted unique integer array `nums`, where all elements are in the inclusive range.

A number `x` is considered missing if `x` is in the range `[lower, upper]` and `x` is not in `nums`.

Return the smallest sorted list of ranges that cover every missing number exactly. That is, no element of `nums` is in any of the ranges, and each missing number is in one of the ranges.

Each range `[a,b]` in the list should be output as:

• `"a->b"` if `a != b`
• `"a"` if `a == b`

Example 1:

```Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: ["2","4->49","51->74","76->99"]
Explanation: The ranges are:
[2,2] --> "2"
[4,49] --> "4->49"
[51,74] --> "51->74"
[76,99] --> "76->99"
```

Example 2:

```Input: nums = [], lower = 1, upper = 1
Output: ["1"]
Explanation: The only missing range is [1,1], which becomes "1".
```

Example 3:

```Input: nums = [], lower = -3, upper = -1
Output: ["-3->-1"]
Explanation: The only missing range is [-3,-1], which becomes "-3->-1".
```

Example 4:

```Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.
```

Example 5:

```Input: nums = [-1], lower = -2, upper = -1
Output: ["-2"]
```

Constraints:

• `-109 <= lower <= upper <= 109`
• `0 <= nums.length <= 100`
• `lower <= nums[i] <= upper`
• All the values of `nums` are unique.

## Explanation

Iterate the numbers and record the latest visited number. Check if there is a gap between the current number and the previous number, if yes, record that gap. In the end, also check if there is a gap between the largest number in the array and the upper value.

## Python Solution

``````class Solution:
def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
results = []

if not nums:
gap = self.helper(lower, upper)
results.append(gap)

return results

prev = lower - 1

for num in nums:
if prev + 1 != num:
gap = self.helper(prev + 1, num - 1)
results.append(gap)
prev = num

if nums[-1] < upper:
gap = self.helper(nums[-1] + 1, upper)
results.append(gap)

return results

def helper(self, left, right):
if left == right:
return str(left)

return str(left) + "->" + str(right)
``````
• Time complexity: ~N
• Space complexity: ~N