[LeetCode] Problem 632 - Smallest Range

Posted on | In ,

You have k lists of sorted integers in ascending order. Find the smallest range 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

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

  1. The given list may contain duplicates, so ascending order means >= here.
  2. 1 <= k <= 3500
  3. -105 <= value of elements <= 105.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public int[] smallestRange(List<List<Integer>> nums) {
    int max = Integer.MAX_VALUE;
    int min = Integer.MIN_VALUE;
    int curMax = Integer.MIN_VALUE;

    PriorityQueue<int[]> minHeap = new PriorityQueue<>(new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return nums.get(o1[0]).get(o1[1]) - nums.get(o2[0]).get(o2[1]);
        }
    });

    for (int i = 0; i < nums.size(); i++) {
        minHeap.offer(new int[] {i, 0});
        curMax = Math.max(curMax, nums.get(i).get(0));
    }

    while (minHeap.size() == nums.size()) {
        int[] pos = minHeap.poll();
        int curMin = nums.get(pos[0]).get(pos[1]);

        if (curMax - curMin < max - min) {
            min = curMin;
            max = curMax;
        }

        if (pos[1] < nums.get(pos[0]).size() - 1) {
            minHeap.offer(new int[] {pos[0], pos[1] + 1});
            curMax = Math.max(curMax, nums.get(pos[0]).get(pos[1] + 1));
        }
    }

    return new int[] {min, max};
}