# C++ solution using Min Heap

• The key idea is that every time we only add value that is on the right and downside of current value and not in the heap in the matrix.

``````class Solution {
private:
struct node {
int r, c, val;
//node(int _r, int _c, int _val) : r(_r), c(_c), val(_val) { };
bool operator < (const node &a)const{
return a.val < val;
}
};
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
priority_queue<node> pq;
vector<vector<bool>> vis(matrix.size(), vector<bool>(matrix[0].size(), false));
int ans = 0;
node cur, nxt;
cur.r = cur.c = 0, cur.val = matrix[0][0];
pq.push(cur);
vis[0][0] = true;
while(k){
cur = pq.top();
pq.pop();
ans = cur.val;
-- k;
int r = cur.r, c = cur.c;
if(r + 1 < matrix.size() && !vis[r + 1][c]){
nxt.r = r + 1, nxt.c = c, nxt.val = matrix[r + 1][c];
vis[nxt.r][nxt.c] = true;
pq.push(nxt);
}
if(c + 1 < matrix[0].size()  && !vis[r][c + 1]){
nxt.r = r, nxt.c = c + 1, nxt.val = matrix[r][c + 1];
vis[nxt.r][nxt.c] = true;
pq.push(nxt);
}
}
return ans;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.