# LeetCode 163: Missing Ranges

## Problem Restatement

We are given an inclusive range:

```python
[lower, upper]
```

We are also given a sorted array `nums`.

The array contains unique integers, and every number in `nums` lies inside `[lower, upper]`.

A number is missing if it is inside `[lower, upper]` but does not appear in `nums`.

We need to return the shortest sorted list of ranges that exactly covers all missing numbers. Each range is represented as:

```python
[start, end]
```

For example, if only `2` is missing, we return:

```python
[2, 2]
```

If all numbers from `4` to `49` are missing, we return:

```python
[4, 49]
```

LeetCode states that `nums` is sorted, unique, and all values are inside the inclusive range `[lower, upper]`. The constraints are `0 <= nums.length <= 100` and `-10^9 <= lower <= upper <= 10^9`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Sorted unique array `nums`, integer `lower`, integer `upper` |
| Output | List of missing ranges |
| Range format | `[start, end]` |
| Interval rule | `lower` and `upper` are included |
| Array rule | Values in `nums` are sorted and unique |

Example function shape:

```python
def findMissingRanges(nums: list[int], lower: int, upper: int) -> list[list[int]]:
    ...
```

## Examples

Example 1:

```python
nums = [0, 1, 3, 50, 75]
lower = 0
upper = 99
```

Numbers covered by `nums` are:

```python
0, 1, 3, 50, 75
```

The missing parts are:

```python
2
4 through 49
51 through 74
76 through 99
```

So the answer is:

```python
[[2, 2], [4, 49], [51, 74], [76, 99]]
```

Example 2:

```python
nums = [-1]
lower = -1
upper = -1
```

The only number in the range is `-1`, and it appears in `nums`.

So there are no missing ranges:

```python
[]
```

Example 3:

```python
nums = []
lower = 1
upper = 5
```

No numbers are present.

So the whole range is missing:

```python
[[1, 5]]
```

## First Thought: Check Every Number

A direct solution is to loop through every integer from `lower` to `upper`.

For each number, check whether it appears in `nums`.

This is not a good idea because the range can be very large.

For example:

```python
lower = -10**9
upper = 10**9
```

That range contains billions of values.

The array length is small, but the numeric interval can be huge.

So we should not iterate over every number in the range.

## Key Insight

Since `nums` is already sorted, missing numbers appear only in gaps.

There are three kinds of gaps:

| Gap location | Missing range |
|---|---|
| Before the first number | `lower` to `nums[0] - 1` |
| Between two adjacent numbers | `nums[i] + 1` to `nums[i + 1] - 1` |
| After the last number | `nums[-1] + 1` to `upper` |

For example:

```python
nums = [0, 1, 3, 50, 75]
```

Between `3` and `50`, the missing range is:

```python
[4, 49]
```

because everything after `3` and before `50` is absent.

## Algorithm

Create an empty answer list:

```python
answer = []
```

If `nums` is empty, return:

```python
[[lower, upper]]
```

Otherwise:

1. Check the gap before `nums[0]`.
2. Check every gap between consecutive numbers.
3. Check the gap after `nums[-1]`.
4. Return the collected ranges.

A gap exists between `a` and `b` when:

```python
b - a > 1
```

The missing range is:

```python
[a + 1, b - 1]
```

## Walkthrough

Use:

```python
nums = [0, 1, 3, 50, 75]
lower = 0
upper = 99
```

Check before the first number:

```python
nums[0] = 0
lower = 0
```

There is no gap before `0`.

Now check adjacent pairs.

Pair `0, 1`:

```python
1 - 0 = 1
```

No missing number.

Pair `1, 3`:

```python
3 - 1 = 2
```

There is a gap:

```python
[2, 2]
```

Pair `3, 50`:

```python
50 - 3 = 47
```

There is a gap:

```python
[4, 49]
```

Pair `50, 75`:

```python
75 - 50 = 25
```

There is a gap:

```python
[51, 74]
```

Check after the last number:

```python
nums[-1] = 75
upper = 99
```

There is a final gap:

```python
[76, 99]
```

Final answer:

```python
[[2, 2], [4, 49], [51, 74], [76, 99]]
```

## Correctness

Because `nums` is sorted, any missing number must lie in one of three places: before the first element, between two adjacent elements, or after the last element.

The algorithm checks the range before the first element. If `nums[0] > lower`, then every integer from `lower` through `nums[0] - 1` is missing, and the algorithm adds exactly that range.

For each adjacent pair `a, b`, there are no elements of `nums` between them. If `b - a > 1`, then every integer from `a + 1` through `b - 1` is missing, and the algorithm adds exactly that range. If `b - a == 1`, no integer can fit between them, so no range is added.

The algorithm also checks the range after the last element. If `nums[-1] < upper`, then every integer from `nums[-1] + 1` through `upper` is missing, and the algorithm adds exactly that range.

These ranges are produced in sorted order and do not overlap. Together, they cover every missing number and no present number. Therefore, the output is exactly the required shortest sorted list of missing ranges.

## Complexity

Let `n` be the length of `nums`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(1)` excluding output | Only a few variables are used |
| Output space | `O(n)` | There can be up to `n + 1` missing ranges |

## Implementation

```python
class Solution:
    def findMissingRanges(
        self,
        nums: list[int],
        lower: int,
        upper: int,
    ) -> list[list[int]]:
        if not nums:
            return [[lower, upper]]

        answer = []

        if nums[0] > lower:
            answer.append([lower, nums[0] - 1])

        for i in range(1, len(nums)):
            prev = nums[i - 1]
            curr = nums[i]

            if curr - prev > 1:
                answer.append([prev + 1, curr - 1])

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

        return answer
```

## Code Explanation

The empty-array case is special:

```python
if not nums:
    return [[lower, upper]]
```

If no values are present, the entire inclusive range is missing.

Then we check whether anything is missing before the first value:

```python
if nums[0] > lower:
    answer.append([lower, nums[0] - 1])
```

Next, scan adjacent pairs:

```python
for i in range(1, len(nums)):
```

For each pair:

```python
prev = nums[i - 1]
curr = nums[i]
```

A missing range exists only when there is space between them:

```python
if curr - prev > 1:
    answer.append([prev + 1, curr - 1])
```

Finally, check after the last value:

```python
if nums[-1] < upper:
    answer.append([nums[-1] + 1, upper])
```

Return the collected ranges:

```python
return answer
```

## Sentinel Implementation

We can also simplify the logic by adding virtual boundaries.

Use:

```python
prev = lower - 1
```

Then scan every number plus a virtual final value:

```python
upper + 1
```

For each current value `curr`, the missing range between `prev` and `curr` is:

```python
[prev + 1, curr - 1]
```

when:

```python
curr - prev > 1
```

Code:

```python
class Solution:
    def findMissingRanges(
        self,
        nums: list[int],
        lower: int,
        upper: int,
    ) -> list[list[int]]:
        answer = []
        prev = lower - 1

        for curr in nums + [upper + 1]:
            if curr - prev > 1:
                answer.append([prev + 1, curr - 1])

            prev = curr

        return answer
```

This version is shorter.

In languages with fixed-width integers, be careful with `lower - 1` and `upper + 1` because of overflow. Python integers are arbitrary precision, so this is safe in Python.

## Testing

```python
def run_tests():
    sol = Solution()

    assert sol.findMissingRanges([0, 1, 3, 50, 75], 0, 99) == [
        [2, 2],
        [4, 49],
        [51, 74],
        [76, 99],
    ]

    assert sol.findMissingRanges([-1], -1, -1) == []
    assert sol.findMissingRanges([], 1, 5) == [[1, 5]]
    assert sol.findMissingRanges([1, 2, 3], 1, 3) == []
    assert sol.findMissingRanges([2], 1, 3) == [[1, 1], [3, 3]]
    assert sol.findMissingRanges([1, 3], 1, 3) == [[2, 2]]
    assert sol.findMissingRanges([-3, -1, 2], -3, 3) == [[-2, -2], [0, 1], [3, 3]]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[0, 1, 3, 50, 75]`, `0`, `99` | Standard example |
| `[-1]`, `-1`, `-1` | No missing number |
| `[]`, `1`, `5` | Whole range missing |
| `[1, 2, 3]`, `1`, `3` | Full coverage |
| `[2]`, `1`, `3` | Missing before and after |
| `[1, 3]`, `1`, `3` | Single missing middle value |
| `[-3, -1, 2]`, `-3`, `3` | Negative and positive gaps |