> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/101-200/missing-ranges.md).

# 163. Missing Ranges

### Description

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`

### Constraints

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

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/missing-ranges/)
* [ProgramCreek](https://www.programcreek.com/2013/03/leetcode-missing-ranges-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="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"
{% endtab %}

{% tab title="Example 2" %}
**Input:** nums = \[], lower = 1, upper = 1

**Output:** \["1"]

**Explanation:** The only missing range is \[1,1], which becomes "1".
{% endtab %}

{% tab title="Example 3" %}
**Input:** nums = \[], lower = -3, upper = -1

**Output:** \["-3->-1"]

**Explanation:** The only missing range is \[-3,-1], which becomes "-3->-1".
{% endtab %}

{% tab title="Example 4" %}
**Input:** nums = \[-1], lower = -1, upper = -1

**Output:** \[]

**Explanation:** There are no missing ranges since there are no missing numbers.
{% endtab %}

{% tab title="Example 5" %}
**Input:** nums = \[-1], lower = -2, upper = -1

**Output:** \["-2"]
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> result = new ArrayList();
        for(int i = 0; i < nums.length; i++) {
            if(lower == nums[i]) {
                lower++;
            } else {
                addRange(lower, (nums[i]-1), result);
                lower = nums[i]+1;
            }
        }
        if(lower <= upper) {
            addRange(lower, upper, result);
        }
        return result;
    }
    
    private void addRange(int low, int high, List<String> result) {
        if(low == high) {
            result.add(String.valueOf(low));
        } else {
            result.add(low  + "->" + high);
        }
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(N), where N is the length of the input array. 
 *    This is because we are only iterating over the array once.
 * Space complexity : O(N), where N is the length of the input array. 
 *    This is because we could have a missing range between each of the 
 *    consecutive element of the input array. Hence, our output list that 
 *    we need to return will be of size N.
 */
 
 class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> result = new ArrayList();
        int n = nums.length;
        
        if(n == 0) {
            addRange(lower, upper, result);
            return result;
        }
        
        if(nums[0] > lower) {
            addRange(lower, nums[0]-1, result);
        }
        
        for(int i = 1; i < n; i++) {
            if(nums[i]-nums[i-1] > 1) {
                addRange(nums[i-1]+1, nums[i]-1, result);
            }
        }
        
        if(nums[n-1] < upper) {
            addRange(nums[n-1]+1, upper, result);
        }
        
        return result;
    }
    
    private void addRange(int low, int high, List<String> result) {
        if(low == high) {
            result.add(String.valueOf(low));
        } else {
            result.add(low  + "->" + high);
        }
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*