632. Smallest Range Covering Elements from K Lists LeetCode Solution

In this guide, you will get 632. Smallest Range Covering Elements from K Lists LeetCode Solution with the best time and space complexity. The solution to Smallest Range Covering Elements from K Lists problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Smallest Range Covering Elements from K Lists solution in C++
4. Smallest Range Covering Elements from K Lists solution in Java
5. Smallest Range Covering Elements from K Lists solution in Python
6. Additional Resources

Problem Statement of Smallest Range Covering Elements from K Lists

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.
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: 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 2:

Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]

Constraints:

nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-105 <= nums[i][j] <= 105
nums[i] is sorted in non-decreasing order.

Complexity Analysis

• Time Complexity: O(n^2\log k), where n = |\texttt{nums}|
• Space Complexity: O(k)

632. Smallest Range Covering Elements from K Lists LeetCode Solution in C++

struct T {
  int i;
  int j;
  int num;  // nums[i][j]
};

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};
  }
};
/* code provided by PROGIEZ */

632. Smallest Range Covering Elements from K Lists LeetCode Solution in Java

class Solution {
  public int[] smallestRange(List<List<Integer>> nums) {
    record T(int i, int j, int num) {} // num := nums[i][j]
    Queue<T> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(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};
  }
}
// code provided by PROGIEZ

632. Smallest Range Covering Elements from K Lists LeetCode Solution in Python

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
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.