Description
leetcode 163
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”].

Note: this problem is ill-defined! The AC solution won’t cover scenario like “upper is smaller that nums[nums.length]” and “lower is greater than nums[0]”. But they do check if upper is larger than nums[-1].
And they check the integer overflow, which is not necessary given the fact the main logic was not even fully covered by test cases.

So if you are new to coding practice, skip this one.

One pass solution

class Solution {

    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> list = new ArrayList<String>();
        long lLower = lower+0L;
        long lUpper = upper+0L;
        
        for(int n : nums){

            long justBelow = n - 1L;
            if(lLower == justBelow) list.add(lLower+"");
            else if(lLower < justBelow) list.add(lLower + "->" + justBelow);
            lLower = n+1L;
        }
        if(lLower == lUpper) list.add(lLower+"");
        else if(lLower < lUpper) list.add(lLower + "->" + lUpper);
        return list;
    }
  
}

imgRuntime: 1ms

class Solution(object):
    def findMissingRanges(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: List[str]
        """
        ret = []
        if nums and lower < nums[0]:
            if lower + 1 == nums[0]:
                ret.append(str(lower))
            else:
                ret.append(str(lower) + "->" + str(nums[0]-1))
                
        for i in xrange(len(nums)-1):
            if nums[i+1] - nums[i] > 1:
                if nums[i+1] - nums[i] == 2:
                    ret.append(str(nums[i]+1))
                else:
                    ret.append(str(nums[i]+1) + "->" + str(nums[i+1]-1))

        if nums and upper > nums[len(nums)-1]:
            if upper == nums[len(nums)-1] + 1:
                ret.append(str(upper))
            else:
                ret.append(str(nums[len(nums)-1]+1) + "->" + str(upper))
        
        if not nums:
            if upper == lower:
                ret.append(str(upper))
            else:
                ret.append(str(lower) + "->" + str(upper))
        return ret

imgRuntime: 18ms