class Solution {
public:
    
    class node{
      public:
        int data;
        int row;
        int col;
        node(int d,int r,int c){
            this->data=d;
            this->row = r;
            this->col = c;
        }
    };
    
    class compare{
        public:
        bool operator()(node*a,node*b){return a->data > b->data;}
    };
    
    vector<int> smallestRange(vector<vector<int>>& nums) {
        vector<int>ans;
        if(nums.size()==0)return ans;
        
        priority_queue<node*,vector<node*>,compare> hp;
        int mini = INT_MAX, maxi = INT_MIN;
        int k = nums.size();
        
        //storing first value.
        for(int i = 0;i<k;i++){
         int ele = nums[i][0];
         maxi = max(maxi,ele);
         mini = min(mini,ele);
         hp.push(new node (ele,i,0));
        }
        
        int st = mini, end = maxi;
        
        while(!hp.empty()){
         
            node * temp = hp.top();
            hp.pop();
            
            mini = temp->data;
            
            if(maxi - mini < end - st){
                st = mini;
                end = maxi;
            }
            
            //add new value to heap and updating maxi also
            
            if(temp->col +1 < nums[temp->row].size()){
                maxi = max(maxi,nums[temp->row][temp->col+1]);
                hp.push(new node(nums[temp->row][temp->col+1],temp->row,temp->col+1));
            }
            else break;
        }
        
        
        ans.push_back(st);
        ans.push_back(end);
        return ans;
        
    }
};

class Solution {
    class Node{
        int arrNo;
        int index;
        int value;
        public Node(int arrNo, int index, int value){
            this.arrNo = arrNo;
            this.index = index;
            this.value = value;
        }
    }
    public int[] smallestRange(List<List<Integer>> nums) {
        //it seems as though there will never be a point where we will remove the current biggest
        //and the next biggest is within the minheap and not the next one added
        
        int max = Integer.MIN_VALUE;
        
		//Add all the first numbers into the priority queue
        PriorityQueue<Node> minheap = new PriorityQueue<>((n1,n2)->n1.value-n2.value);
        for(int i = 0; i < nums.size(); i++){
            List<Integer> num = nums.get(i);
            minheap.add(new Node(i, 0, num.get(0)));
            max = Math.max(max, num.get(0));
        }
        
        int min = minheap.peek().value;
        int[] ans = new int[]{min, max};
        int range = max - min;
        
        //we will then iterate through and update ans accordingly if range is smaller than past ranges
        //Note that the next node can still be the smallest.
        Node nextNode = minheap.poll();
        while(nextNode.index + 1 < nums.get(nextNode.arrNo).size()){
            int nextArr = nextNode.arrNo;
            int nextIndex = nextNode.index + 1;
            Node newNode = new Node(nextArr, nextIndex, nums.get(nextArr).get(nextIndex));
            
            //add the new Node and check the range changes
            minheap.offer(newNode);
            max = Math.max(max, newNode.value);
            min = minheap.peek().value;
            if(range > max-min){
                range = max - min;
                ans = new int[]{min, max};
            }
            
            nextNode = minheap.poll();
        }
        
        return ans;
    }
}
 

from heapq import heappush, heappop
class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        n = len(nums)
        next_idx = [0]*n
        # cur_val, next_idx, sublist_idx
        min_idx_pq = []
        cur_min = float('inf')
        cur_max = float('-inf')
        for i in range(n):
            heappush(min_idx_pq, (nums[i][0],0,i))
            cur_min = min(cur_min,nums[i][0])
            cur_max = max(cur_max,nums[i][0])
        smallest_interval = [cur_min,cur_max]
        smallest_interval_len = cur_max - cur_min
        while True:
            cur_val, next_idx, sublist_idx = heappop(min_idx_pq)
            next_idx += 1
            if next_idx == len(nums[sublist_idx]):
                break
            cur_val = nums[sublist_idx][next_idx]
            heappush(min_idx_pq,(cur_val,next_idx,sublist_idx))
            cur_min = min_idx_pq[0][0]
            cur_max = max(cur_max,cur_val)
            cur_interval = cur_max - cur_min
            if cur_interval < smallest_interval_len:
                smallest_interval_len = cur_interval
                smallest_interval = [cur_min,cur_max]
        return smallest_interval