Advertisement
imashutosh51

Kth smallest element in a sorted matrix

Oct 16th, 2022
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. /*
  2. Logic:
  3. We can declare a min heap and put first elements from all the columns along with cordinates.
  4. min heap will sort the elements based on the first component of each element.
  5. pop top element from min heap and put the next element from that column only.
  6. this way we will get elements one by one and return the kth element.
  7. */
  8.  
  9. class Solution {
  10. public:
  11.     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;
  12.         int n=matrix.size();
  13.         for(int j=0;j<n;j++){
  14.             q.push({matrix[0][j],{0,j}});
  15.         }
  16.         int count=0;
  17.         while(!q.empty()){
  18.             int val=q.top().first;
  19.             pair<int,int> temp=q.top().second;
  20.            
  21.             if(++count==k) return val;
  22.             q.pop();
  23.             if(temp.first+1<n){ q.push({matrix[temp.first+1][temp.second],{temp.first+1,temp.second}});}
  24.         }
  25.         return 0;
  26.     }
  27. };
  28.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement