Smallest Range

LeetCode Q 632 - Smallest Range

You have k lists of sorted integers in ascending order. Find the smallestrange that includes at least one number from each of the k lists.

We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.

Example 1:
Input:[[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].

Note:

• The given list may contain duplicates, so ascending order means >= here.
• 1 <= k <= 3500
• -105 <= value of elements <= 105.
• For Java users, please note that the input type has been changed to List<List>. And after you reset the code template, you’ll see this point.

Solution :

This question is similar to Merge k Sorted Lists.

We use n pointers to traverse all the nums in each list. At each step, we only move the pointer that points to the min value and update the minRange.

Code:

public int[] smallestRange(List<List<Integer>> nums) {
	
	PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (a[2] - b[2]));

	int max = Integer.MIN_VALUE, left = 0, right = Integer.MAX_VALUE;
	for (int i = 0; i < nums.size(); i++) {
		pq.offer(new int[] {i, 0, nums.get(i).get(0)});
		max = Math.max(max, nums.get(i).get(0));
	}	

	while (pq.size() == nums.size()) {
		int[] curr = pq.poll();
		int r = curr[0], c = curr[1], minVal = curr[2];
		if (right - left > max - minVal) { // range > curr range
			left = minVal; // update left border of range
			right = max; // update right border
		}

		if (c + 1 < nums.get(r).size()) {
			pq.offer(new int[]{r, c + 1, nums.get(r).get(c + 1)});
			max = Math.max(max, nums.get(r).get(c + 1));
		}
	}	

	return new int[]{left, right};
}