> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/google/163-missing-ranges.md).

# 163 Missing Ranges

## 163. [Missing Ranges](https://leetcode.com/problems/missing-ranges/description/)

## 1. Question

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 andupper= 99, return`["2", "4->49", "51->74", "76->99"].`

## 2. Implementation

**(1) Scan Line**

```
class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<>();

        for (int i = 0; i <= nums.length; i++) {
            long start = i == 0 ? lower : (long)nums[i - 1] + 1;
            long end = i == nums.length ? upper : (long)nums[i] - 1;
            addMissingRange(res, start, end);
        }
        return res;
    }

    public void addMissingRange(List<String> res, long start, long end) {
        if (start > end) {
            return;
        }

        if (start == end) {
            res.add(start + "");
        }
        else {
            res.add(start + "->" + end);
        }
    }
}
```

## 3. Time & Space Complexity

**Scan Line:** 时间复杂度O(n), 空间复杂度O(n)