Wednesday, August 19, 2015

Leetcode: Missing Ranges

Given a sorted integer array where the range of elements are [lowerupper] 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"].
Understand the problem:
The problem itself is not hard at all. The key is to handle several corner cases. e.g. 
 -- If the array is empty, the missing ranges should be from lower to upper, inclusive. 
 -- For the leading missing range, e.g. -2 , [-1], -1. The output should be "-2". Note that the lower bound is inclusive. 
 -- For the trailing missing range, e.g. -2, [-2], 1, the output should be "-1->1". The upper bound is inclusive as well. 

Code (Java):
public class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> result = new ArrayList<String>();
        if (nums == null || nums.length == 0) {
            outputToResult(lower, upper, result);
            return result;
        }
        
        // leading missing range
        if (nums[0] - lower > 0) {
            outputToResult(lower, nums[0] - 1, result);
        }
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] > 1) {
                outputToResult(nums[i - 1] + 1, nums[i] - 1, result);
            }
        }
        
        // trailing missage ranges
        if (upper - nums[nums.length - 1] > 0) {
            outputToResult(nums[nums.length - 1] + 1, upper, result);
        }
        
        return result;
    }
    
    private void outputToResult(int start, int end, List<String> result) {
        StringBuffer sb = new StringBuffer();
        if (start == end) {
            sb.append(start);
        } else {
            sb.append(start + "->" + end);
        }
        
        result.add(sb.toString());
    }
}

1 comment:

  1. [-2147483648,2147483647]
    -2147483648
    2147483647

    Fails for this case

    ReplyDelete