Code giving wrong output

#1

Heyy i tried to code according to the explanantion given in the video but its not working. Please tell what’s wrong.

#2

class comp
{
public:
bool operator()(pair<int, pair<int, int>> &a, pair<int, pair<int, int>> &b)
{
return a.first > b.first;
}
};
int kthSmallest(vector<vector>& matrix, int k) {
int n = matrix.size();
int m = matrix[0].size();
int ans= matrix[0][0];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, comp> p;
p.push(make_pair(matrix[0][0], make_pair(0,0)));
while(k–)
{
auto top = p.top();
p.pop();
if(top.second.second +1 <m)
{ p.push(make_pair(matrix[top.second.first][top.second.second +1], make_pair(top.second.first,top.second.second +1)));
matrix[top.second.first][top.second.second +1] = INT_MAX;}
if(top.second.first +1 <n)
{
p.push(make_pair(matrix[top.second.first +1][top.second.second], make_pair(top.second.first +1 ,top.second.second)));
matrix[top.second.first +1][top.second.second] = INT_MAX;}
ans = top.first;

}
return ans;
}
this is my implementation of the question
i will just point out the difference
u do not have to build the heap out of the first element of each row
u do not have to push the down and right of each element just the required one

#3

I am not able to understand your approach. Please tell me the implementation according to the video lecture.

#4

what my code does is simple, it is actually similar to the logic that u have used,
firrst in my priority queue§ i push (0th element, (0,0))
then while(k–)
i pop the top element for p
now i see the index of the element popped, if it’s column+1<m(total columns) i push m[i][j+1] if the popped element was m[i][j] and mark it as INT_MAX
then i check it’s row+1 should also be in bound, if it is in bound i push m[i+1][j] into p and mark it as INT_MAX
then i make my answer as this element which was m[i][j] as my answer
at the end of the loop i return my answer
//important note: this considers k<nm if k == nm return last element directly
further optimisition (completely upto you, not necessary)
hint: if k> nm/2 u can do this nm-k and start for the last element directly, now it will become kth largest element problem

#5

Okay thanks a lot. This helped.