Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.

For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return [“2”, “4->49”, “51->74”, “76->99”].

O(n) time O(1) space solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        if (lower > upper)
            return null;
        List<String> res = new LinkedList<>();
        
        int next = lower;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= next) {
                if (nums[i] == next) {
                    next++;
                    continue;
                } else {
                    res.add(findMissing(next, nums[i] - 1));
                    next = nums[i] + 1;
                }
            }
        }
        if (next <= upper)
            res.add(findMissing(next, upper));
        return res;
    }
    
    public String findMissing(int low, int high) {
        return low == high ? String.valueOf(low) : String.format("%d->%d", low, high);
    }
}