Accepted Java Solution with Explanation


  • 0
    A

    It's important to locate sub-interval within A that falls between [lower, upper], and we should do this in O(logn) instead of O(n) (maybe LC didn't check this?)
    This is my accepted Java solution:

    /**
     * first, handle special cases where A is empty or
     * A is complete out of range [lower, upper].
     * Then, use binary search to locate the interval on A that is
     * within range [lower, upper].
     * Last:
     * 1. check lower vs first element of interval.
     * 2. iterate through each element and compare against prev.
     * 3. check last element of interval vs upper.
     */
    public List<String> findMissingRanges(int[] A, int lower, int upper) {
        List<String> results = new ArrayList<String>();
        
    	// index of first element >= lower
    	int head = firstLargerEqual(A, 0, A.length-1, lower);
    	// index of last element <= upper
        int tail = lastLessEqual(A, 0, A.length-1, upper);
        if (head < 0 && tail < 0)
            add(lower, upper, results);
        else {
            add(lower, A[head]-1, results);
            for (int i = head+1; i <= tail; i++)
                add(A[i-1]+1, A[i]-1, results);
            add(A[tail]+1, upper, results);
        }
        
        return results;
    }
    
    // return index of first element >= target; if none, return -1.
    private int firstLargerEqual(int[] array, int start, int end, int target) {
        if (start > end)
            return -1;
        int mid = start + (end - start)/2;
        if (array[mid] >= target) {
            if (mid - 1 < start || array[mid-1] < target)
                return mid;
            else
                return firstLargerEqual(array, start, mid-1, target);
        } else {
            return firstLargerEqual(array, mid+1, end, target);
        }
    }
    
    // return index of last element <= target; if none, return -1.
    private int lastLessEqual(int[] array, int start, int end, int target) {
    	if (start > end)
    			return -1;
    	int mid = start + (end-start)/2;
    	if (array[mid] <= target) {
    		if (mid + 1 > end || array[mid+1] > target)
    			return mid;
    		else
    			return lastLessEqual(array, mid+1, end, target);
    	} else {
    		return lastLessEqual(array, start, mid-1, target);
    	}
    }
    
    // add a range to list
    private void add(int num1, int num2, List<String> results) {
        if (num1 <= num2) {
            if (num1 == num2)
                results.add(String.valueOf(num1));
            else
                results.add(num1 + "->" + num2);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.