Skip to content

632. Smallest Range Covering Elements from K Lists 👍

  • Time: $O(n^2\log k)$, where $n = |\texttt{nums}|$
  • Space: $O(k)$
 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
35
36
37
38
39
40
41
42
struct T {
  int i;
  int j;
  int num;  // nums[i][j]
  T(int i, int j, int num) : i(i), j(j), num(num) {}
};

class Solution {
 public:
  vector<int> smallestRange(vector<vector<int>>& nums) {
    auto compare = [&](const T& a, const T& b) { return a.num > b.num; };
    priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);
    int mn = INT_MAX;
    int mx = INT_MIN;

    for (int i = 0; i < nums.size(); ++i) {
      const int num = nums[i][0];
      minHeap.emplace(i, 0, num);
      mn = min(mn, num);
      mx = max(mx, num);
    }

    int minRange = mn;
    int maxRange = mx;

    while (minHeap.size() == nums.size()) {
      const auto [i, j, _] = minHeap.top();
      minHeap.pop();
      if (j + 1 < nums[i].size()) {
        minHeap.emplace(i, j + 1, nums[i][j + 1]);
        mx = max(mx, nums[i][j + 1]);
        mn = minHeap.top().num;
        if (mx - mn < maxRange - minRange) {
          minRange = mn;
          maxRange = mx;
        }
      }
    }

    return {minRange, maxRange};
  }
};

 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
35
36
37
38
39
40
41
42
43
44
class T {
  public int i;
  public int j;
  public int num; // nums[i][j]
  public T(int i, int j, int num) {
    this.i = i;
    this.j = j;
    this.num = num;
  }
}

class Solution {
  public int[] smallestRange(List<List<Integer>> nums) {
    Queue<T> minHeap = new PriorityQueue<>((a, b) -> a.num - b.num);
    int mn = Integer.MAX_VALUE;
    int mx = Integer.MIN_VALUE;

    for (int i = 0; i < nums.size(); ++i) {
      final int num = nums.get(i).get(0);
      minHeap.offer(new T(i, 0, num));
      mn = Math.min(mn, num);
      mx = Math.max(mx, num);
    }

    int minRange = mn;
    int maxRange = mx;

    while (minHeap.size() == nums.size()) {
      final int i = minHeap.peek().i;
      final int j = minHeap.poll().j;
      if (j + 1 < nums.get(i).size()) {
        minHeap.offer(new T(i, j + 1, nums.get(i).get(j + 1)));
        mx = Math.max(mx, nums.get(i).get(j + 1));
        mn = minHeap.peek().num;
      }
      if (mx - mn < maxRange - minRange) {
        minRange = mn;
        maxRange = mx;
      }
    }

    return new int[] {minRange, maxRange};
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def smallestRange(self, nums: List[List[int]]) -> List[int]:
    minHeap = [(row[0], i, 0) for i, row in enumerate(nums)]
    heapq.heapify(minHeap)

    maxRange = max(row[0] for row in nums)
    minRange = heapq.nsmallest(1, minHeap)[0][0]
    ans = [minRange, maxRange]

    while len(minHeap) == len(nums):
      num, r, c = heapq.heappop(minHeap)
      if c + 1 < len(nums[r]):
        heapq.heappush(minHeap, (nums[r][c + 1], r, c + 1))
        maxRange = max(maxRange, nums[r][c + 1])
        minRange = heapq.nsmallest(1, minHeap)[0][0]
        if maxRange - minRange < ans[1] - ans[0]:
          ans[0], ans[1] = minRange, maxRange

    return ans