Smallest Range Covering Elements from K Lists LeetCode Solution

Last updated on January 29th, 2025 at 02:13 am

Here, we see the Smallest Range Covering Elements from K Lists LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Hash Table, String, Two-Pointers

Level of Question

Hard

Smallest Range Covering Elements from K Lists LeetCode Solution

Smallest Range Covering Elements from K Lists LeetCode Solution

1. 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]

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is K-way Merge. This pattern is commonly used to merge multiple sorted arrays or lists into a single sorted array or to solve problems that involve processing elements from multiple sorted arrays simultaneously. The code uses a min-heap (priority queue) to efficiently track the smallest element across multiple lists and iteratively processes the next smallest element.

3. Code Implementation in Different Languages

3.1 Smallest Range Covering Elements from K Lists 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};
    }
};

3.2 Smallest Range Covering Elements from K Lists 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.3 Smallest Range Covering Elements from K Lists 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;
};

3.4 Smallest Range Covering Elements from K Lists 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

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(n * log(k))O(k)
JavaO(n * log(k))O(k)
JavaScriptO(n * log(k))O(k)
PythonO(n * log(k))O(k)
  • K-way Merge is the core pattern here, leveraging a min-heap to efficiently track the smallest element across multiple lists.
  • The algorithm ensures that the smallest range containing at least one number from each list is found in an optimal manner.
  • The time and space complexities are consistent across all implementations (C++, Java, JavaScript, Python) because the underlying logic and data structures (priority queue or heap) are the same.
Scroll to Top