Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Logic:
- We can declare a min heap and put first elements from all the columns along with cordinates.
- min heap will sort the elements based on the first component of each element.
- pop top element from min heap and put the next element from that column only.
- this way we will get elements one by one and return the kth element.
- */
- class Solution {
- public:
- int kthSmallest(vector<vector<int>>& matrix, int k) { priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> q;
- int n=matrix.size();
- for(int j=0;j<n;j++){
- q.push({matrix[0][j],{0,j}});
- }
- int count=0;
- while(!q.empty()){
- int val=q.top().first;
- pair<int,int> temp=q.top().second;
- if(++count==k) return val;
- q.pop();
- if(temp.first+1<n){ q.push({matrix[temp.first+1][temp.second],{temp.first+1,temp.second}});}
- }
- return 0;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement