Sunday, January 11, 2015

LeetCode 163: Missing Ranges

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"].
public class Solution {
    public List<String> findMissingRanges(int[] A, int lower, int upper) {
        List<String> result = new LinkedList<>();
        
        int n = A.length;
        
        if (n == 0)
        {
            findMissingPart(result, lower, upper);
            return result;
        }
        
        // Process the starting section
        findMissingPart(result, lower, A[0]-1);
        
        // Process the middle section
        for (int i = 0; i < n-1; i++)
            findMissingPart(result, A[i]+1, A[i+1]-1);
            
        // Process the ending section
        findMissingPart(result, A[n-1]+1, upper);
        
        return result;
    }
    
    private void findMissingPart(List<String> result, int lo, int hi)
    {
        if (lo == hi)
        {
            String ret = Integer.toString(lo);
            result.add(ret);
        }
        else if (lo < hi)
        {
            String ret = Integer.toString(lo);
            ret += "->";
            ret += Integer.toString(hi);
            result.add(ret);
        }        
    }
}

No comments:

Post a Comment