163. Missing Ranges

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

Solution:

We go through the input array and check lower with each element - 1.

If lower == element - 1, we add the range of one number.

If lower < element - 1, we add the range from lower to element - 1.

After adding a range, we update lower to element + 1.

Need to check boundary to avoid overflow.

The time complexity is O(n) and the space complexity is O(1).



Code:

public class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> result = new ArrayList<>();
        for (int num : nums) {
            if (num == Integer.MIN_VALUE) {
                lower = num + 1;
                continue;
            }
            if (lower == num - 1) {
                result.add(lower + "");
            }
            else if (lower < num - 1) {
                result.add(lower + "->" + (num - 1));
            }
            if (num == Integer.MAX_VALUE) {
                return result;
            }
            lower = num + 1;
        }
        if (lower == upper) {
            result.add(lower + "");
        }
        else if (lower < upper) {
            result.add(lower + "->" + upper);
        }
        return result;
    }
}