LeetCode: Missing Ranges

// 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"].
import java.util.*;

public class MissingRanges {

    public static List<String> findMissingRanges(int[] nums, int lower, int upper) {
        ArrayList<String> result = new ArrayList<String>();
     
        for(int i = 0; i <= nums.length; i++) {
            long start = i == 0 ? lower : (long)nums[i - 1] + 1;
            long end = i == nums.length ? upper : (long)nums[i] - 1;
            addMissing(result, start, end);
        }
        return result;
    }
 
    static void addMissing(ArrayList<String> result, long start, long end) {
System.out.println("adding range:"+start+"..."+end);
        if(start > end) {
            return;
        } else if(start == end) {
            result.add(start + "");
        } else {
            result.add(start + "->" + end);
        }
    }

public static List<String> findMissingRanges2(int[] nums, int lower, int upper) {
int ind = 0;
ArrayList<String> result = new ArrayList<String>();
for(int i=lower; i<=upper; i++){
if(ind<nums.length && nums[ind]>i){
addMissing(result, i, nums[ind]-1);
i = nums[ind];//move i till it reaches nums[mid] because i to nums[mid]-1 is already added
}else if(ind>=nums.length && i<upper){
addMissing(result, i, upper);
i=upper;//no more ranges to be added, the array is exhausted
}
ind++;
}
return result;
}

public static void main(String[] args){
int[] nums = {10, 11, 13, 50, 75};
List<String> res1 = findMissingRanges(nums, 0, 99);
List<String> res2 = findMissingRanges2(nums, 0, 99);
System.out.println(Arrays.toString(res1.toArray()));
System.out.println(Arrays.toString(res2.toArray()));
}
}

No comments:

Post a Comment