Last updated on October 9th, 2024 at 06:14 pm

Here, We see Smallest Range Covering Elements from K Lists LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Smallest Range Covering Elements from K Lists LeetCode Solution

Problem Statement

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]

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

class Solution {
public:
    struct node {
        int data, row, column;
        node(int value, int i, int j) : data(value), row(i), column(j) {}
    };
    struct comparator {
        bool operator() (node a, node b) {
            return a.data > b.data;
        }
    };
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int k = nums.size();
        priority_queue<node, vector<node>, comparator> minHeap;
        int currMin = INT_MAX, currMax = INT_MIN, currRange = INT_MAX;
        for(int i = 0; i < k; ++i) {
            currMax = max(currMax, nums[i][0]);
            node temp(nums[i][0], i, 0);
            minHeap.push(temp);
        }
        int start = currMin, end = currMax;
        while(true) {
            node min = minHeap.top();
            minHeap.pop();
            currMin = min.data;
            if(currMax - currMin < currRange) {
                start = currMin;
                end = currMax;
                currRange = currMax - currMin;
            }
            if(min.column + 1 == nums[min.row].size())
                break;
            node next(nums[min.row][min.column + 1], min.row, min.column + 1);
            minHeap.push(next);
            if(next.data > currMax)
                currMax = next.data;
        }
        return {start, end};
    }
};

2. Smallest Range Covering Elements from K Lists LeetCode Solution Java

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int[] res = new int[2];
        int minx=Integer.MAX_VALUE;
        int maxy=Integer.MIN_VALUE;
        int minRange=Integer.MAX_VALUE;
        PriorityQueue<int[]> pq=new PriorityQueue<>((i,j) -> 
        i[0] - j[0]                                 
        );
        for(int i=0;i<nums.size();i++)
        {
            if(nums.get(i).get(0)>maxy)
                maxy=nums.get(i).get(0);
            pq.offer(new int[] {nums.get(i).get(0),i,0});
        }
        
        while(!pq.isEmpty())
        {
            int[] min=pq.poll();
            int i=min[1];
            int j=min[2];
            if(maxy-min[0] < minRange)
            {
                minRange=maxy-min[0];
                res[0]=min[0];
                res[1]=maxy;
            }
            if(i<nums.size() && j+1<nums.get(i).size())
            {
                pq.offer(new int[] {nums.get(i).get(j+1),i,j+1});
                if(nums.get(i).get(j+1)>maxy)
                    maxy=nums.get(i).get(j+1);
            }
            else
                break;
        }
        return res;
    }
}

3. Smallest Range Covering Elements from K Lists LeetCode Solution JavaScript

var smallestRange = function(nums) {
    const minPQ = new MinPriorityQueue({
        priority: a => a[2] 
    });
    let minRange = Number.MAX_VALUE;
    for (let i=0;i<nums.length;i++) {
        minPQ.enqueue([i, 0, nums[i][0]]);
    }
    let ans = [];
    while (!minPQ.isEmpty()) {
        const range =  minPQ.back().element[2] - minPQ.front().element[2];
        if (minRange > range) {
            minRange = range;
            ans = [minPQ.front().element[2], minPQ.back().element[2]];
        }
        
        const [listIndex, listIterator, currentValue] = minPQ.front().element;
        if (listIterator + 1 < nums[listIndex].length) {
            minPQ.dequeue();
            minPQ.enqueue([listIndex,listIterator + 1, nums[listIndex][listIterator + 1]]);
        } else {
            break;
        }
    }
    return ans;
};

4. Smallest Range Covering Elements from K Lists Solution Python

class Solution(object):
    def smallestRange(self, nums):
        n = len(nums)  
        pq = []
        ma = 0
        for i in range(n):
            heappush(pq, (nums[i][0] , i, 0))
            ma = max(ma , nums[i][0])
        ans = [pq[0][0] , ma]
        while True:
            _,i,j = heappop(pq)
            if j == len(nums[i])-1:
                break
            next_num = nums[i][j+1]
            ma = max( ma , next_num)
            heappush(pq,(next_num, i , j+1))
            if ma-pq[0][0] < ans[1] - ans[0]:
                ans= [pq[0][0], ma]
        return ans