632. Smallest Range Covering Elements from K Lists

Problem

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

• -10^5 <= nums[i][j] <= 10^5

• nums[i] is sorted in non-decreasing order.

Solution (Java)

class Solution {
    static class Triplet implements Comparable<Triplet> {
        int value;
        int row;
        int idx;

        Triplet(int value, int row, int idx) {
            this.value = value;
            this.row = row;
            this.idx = idx;
        }

        public int compareTo(Triplet obj) {
            return this.value - obj.value;
        }
    }

    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<Triplet> pq = new PriorityQueue<>();
        int maxInPq = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            pq.add(new Triplet(nums.get(i).get(0), i, 0));
            if (maxInPq < nums.get(i).get(0)) {
                maxInPq = nums.get(i).get(0);
            }
        }
        int rangeSize = maxInPq - Objects.requireNonNull(pq.peek()).value + 1;
        int rangeLeft = Objects.requireNonNull(pq.peek()).value;
        int rangeRight = maxInPq;
        while (true) {
            Triplet nextNumber = pq.remove();
            if (nextNumber.idx + 1 < nums.get(nextNumber.row).size()) {
                int val = nums.get(nextNumber.row).get(nextNumber.idx + 1);
                if (val > maxInPq) {
                    maxInPq = val;
                }
                pq.add(new Triplet(val, nextNumber.row, nextNumber.idx + 1));
                if (maxInPq - Objects.requireNonNull(pq.peek()).value + 1 < rangeSize) {
                    rangeSize = maxInPq - pq.peek().value + 1;
                    rangeLeft = maxInPq;
                    rangeRight = pq.peek().value;
                }
            } else {
                break;
            }
        }
        int[] answer = new int[2];
        answer[0] = rangeLeft;
        answer[1] = rangeRight;
        return answer;
    }
}

Solution (Python3)

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

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).