163. Missing Ranges

T: O(n)
S: O(n)

```java
class Solution {
    public List<List<Integer>> findMissingRanges(int[] nums, int lower, int upper) {
        if (nums.length == 0) { // for ex3, ex4
            return Arrays.asList(Arrays.asList(lower, upper));
        }
        if (lower == upper) { // for ex2
            return new ArrayList<>();
        }
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<>();

        if (lower < nums[0]) { // for ex5: first part 
            result.add(Arrays.asList(lower, nums[0]-1));
        }
        for (int i = 0; i < n-1; i++) {
            if (nums[i]+1 == nums[i+1]) {
                continue;
            }
            result.add(Arrays.asList(nums[i]+1, nums[i+1]-1));
        }
        if (nums[n-1] != upper) { // <- for ex5: last part
            result.add(Arrays.asList(nums[n-1]+1, upper)); // for ex1, last part
        }

        return result;
    }
}

/***
T: O(n)
S: O(n)

ex1:
nums = [0,1,3,50,75], lower = 0, upper = 99
ans: [[2,2],[4,49],[51,74],[76,99]]

ex2:
[-1]
-1
-1
ans: []

ex3:
[]
1
1
ans: [[1,1]]

ex4:
[]
1
99
ans: [[1,99]]

ex5:
[-1]
-2
-1
ans: [[-2,-2]]

 */
```