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]
The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.
package com.omt.learn.algo; import java.util.Set; import java.util.TreeSet; public class LengthOfArray { public static void main(String args[]) { int[][] arrayOfArray = { { 2, 10, 15, 24, 26 }, { 0, 9, 12, 20 }, { 4, 18, 22, 30 } }; int[] selectedArray = calculateMinDistance(arrayOfArray); System.out.print("[ "); for (int i : selectedArray) { System.out.print(i + " "); } System.out.println("]"); } private static int[] calculateMinDistance(int[][] arrays) { Integer arrayOfSet[] = combineSortedArray(arrays); int minRangeFoundForSelectedArray = arrayOfSet[arrayOfSet.length - 1] - arrayOfSet[0]; int arrayLength = arrays.length; int selectedArray[] = new int[arrayLength]; int validCount = (arrayLength) * (arrayLength + 1) / 2; int count = 0; while ((count + arrayLength) < arrayOfSet.length) { int[] tempArray = new int[arrayLength]; for (int i = 0; i < arrayLength; i++) { tempArray[i] = arrayOfSet[i + count]; } if (((tempArray[arrayLength - 1] - tempArray[0]) <= minRangeFoundForSelectedArray) && isCoverAllArrayCount(tempArray, arrays) == validCount) { selectedArray = tempArray; minRangeFoundForSelectedArray = tempArray[arrayLength - 1] - tempArray[0]; } count++; } return selectedArray; } private static int isCoverAllArrayCount(int[] selectedArray, int[][] arrays) { int count = 0; for (int i = 0; i < arrays.length; i++) { int[] singleArray = arrays[i]; loopJ: for (int j : singleArray) { for (int selectedInt : selectedArray) { if (j == selectedInt) { count += i + 1; break loopJ; } } } } return count; } private static Integer[] combineSortedArray(int arrays[][]) { Set<Integer> set = new TreeSet<Integer>(); for (int[] a : arrays) { for (int number : a) { set.add(number); } } Integer arrayOfSet[] = set.toArray(new Integer[set.size()]); return arrayOfSet; } }