163. Missing Ranges (1)

Link

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

Example:

Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
Output: ["2", "4->49", "51->74", "76->99"]

Solution

class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<String>();
        int next = lower; //the upper bound of current contiguious interval
        for (int i = 0; i < nums.length; i++) {
            // 1. We don't need to add [Integer.MAX_VALUE, ...] to result
            if(lower == Integer.MAX_VALUE) return res;
            
            //Still inside the contiguious interval
            if (nums[i] < next) {
                continue;
            }
            //Reach the upper bound of interval
            //Increase the upper bound of contiguious interval 
            //to see if next num is still inside the contiguious interval
            if (nums[i] == next) {
                next++;
                continue;
            }
            //nums[i] is out of the contiguious inerval 
            //There shall be a missing range between next and nums[i]-1
            else if (nums[i] > next){
                res.add(getRange(next, nums[i] - 1));
            }
            // 2. We don't need to proceed after we have process Integer.MAX_VALUE in array
            if(nums[i] == Integer.MAX_VALUE) return res;
            next = nums[i] + 1;
        }
        
        if (next <= upper) {
            res.add(getRange(next, upper));
        }
        return res;
    }
    
    public String getRange(int n1, int n2) {
        return n1 == n2 ? String.valueOf(n1) : String.format("%d->%d" , n1, n2);
    }
        
}