This is a fun problem. You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists. For example... List 1: [4, 10, 15, 24, 26] List 2: [0, 9, 12, 20] List 3: [5, 18, 22, 30] should return 24,20,22 (because the smallest range is 20--24). List 1: [1,2,3,80] List 2: [1,2,3,90,200] List 3: …

SmallestRange

 
/*
 * You have k lists of sorted integers. This method returns the smallest range that includes at least one number from each of the k lists
 * @return int[] a list that demosntrates the range with values from each list
 * @param lists a list that contains K sorted lists of int[]s 
 */
public int[] smallestRange(List<int[]> lists){
    int[] mins = new int[lists.size()]; //the current minimum value from each int[] in lists
    int[] indexes = new int[lists.size()]; //the current index for each array in lists

    for(int i =0; i < mins.length; i ++){
        if(lists.get(i) == null || lists.get(i).length == 0)//all int[] MUST start with one element
            return null;

        mins[i] = lists.get(i)[0];
        indexes[i] = 1;;
    }

    int[] rangeReturn = findRange(mins);
    int index = rangeReturn[0];//the current index of the list with the smallest value

    int[] bestRangeValues = mins.clone();;
    bestRangeValues=mins.clone();
    int bestRange = rangeReturn[1];
    
    //loop until one of the lists is out of bounds, then stop
    while(indexes[index] < lists.get(index).length){
        mins[index] = lists.get(index)[indexes[index]];//get the minimum value from the list with the smallest number
        indexes[index] ++;
        
        rangeReturn = findRange(mins);
        //if the new range is better, store those values
        if(rangeReturn[1] < bestRange)
            bestRangeValues = mins.clone();
        index = rangeReturn[0];
    }

    return bestRangeValues;

}

/*
 * a helper function that will compute the range of a given int[].  in addition, it will provide the index that contains the minimum value
 * @return int[]  [0] = the index containing the minimum value, [1]= the range 
 */
private int[] findRange(int[] x){
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    int[] returnStuff = new int[2]; //[0] = min index, [1]= range
    for(int i =0; i < x.length; i++){
        if(x[i] < min){
            min = x[i];
            returnStuff[0] = i;
        }
        if(x[i] > max){
            max=x[i];
        }
    }
    returnStuff[1] = max-min;
    return returnStuff;
}