This page explains Java solution to problem Smallest Range Covering Elements from K Lists
using Priority Queue
data structure.
You have k
lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k
lists.
Example 2:Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]
Explanation: List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].
Example 3:Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]
Example 4:Input: nums = [[10,10],[11,11]]
Output: [10,11]
Input: nums = [[1],[2],[3],[4],[5],[6],[7]]
Output: [1,7]
package com.vc.hard;
import java.util.*;
class SmallestRangeCoveringElementsFromKLists {
public int[] smallestRange(List<List<Integer>> nums) {
if(nums == null || nums.size() == 0) return new int[0];
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
public int compare(int[] x, int[] y) {
return Integer.compare(x[2], y[2]);
}
});
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for(int i = 0; i < nums.size(); i++) {
int val = nums.get(i).get(0);
pq.offer(new int[]{i, 0, val});
min = Math.min(min, val);
max = Math.max(max, val);
}
int start = min;
int end = max;
int minRange = end - start;
while(pq.size() == nums.size()) {
int[] q = pq.poll();
int row = q[0];
int col = q[1];
int val = q[2];
if(max - val < minRange) {
minRange = max - val;
min = val;
start = min;
end = max;
}
if(col + 1 < nums.get(row).size()) {
int newVal = nums.get(row).get(col + 1);
pq.offer(new int[]{row, col + 1, newVal});
max = Math.max(max, newVal);
}
}
return new int[]{start, end};
}
}
O(N * Log K) Where
K is size of nums
N is max of (nums[0].size(), nums[1].size() .... nums[k].size())
O(K) Where
K is length of nums
N is max of (nums[0].size(), nums[1].size() .... nums[k].size())