LeetCode: Kth Smallest Element in a Sorted Matrix

Hi guys,

My name is Michael Lin and this is my programming youtube channel. I like C++ and please message me or comment on what I should program next. It really helps out a lot.

Rate, Comment, Subscribe

Subscribe to my singing channel:

Personal Accounts:
Instagram: @michaellin250
Twitter: @Michaellin250

#kthSmallestElement #sortedMatrix #heaps

[sentinel-yl]

Both min and max heap have the same time complexity O(N * log(N)) for N = total number of elements in the matrix.

Both min and max heap go through all the elements (O(N)). For the max heap you add (O(log(N))) at least k elements and pop (O(log(N))) the elements when you add them if size > k and the new element is lower (something that doesn't occur very frequently if you iterate from top left to bottom right), for min heap you add every time and pop k elements at the end. So, even though max heap is faster, it still has the same worst case time complexity.

If k = N, then both solutions have the same memory complexity too, i.e. O(N), as max heap is O(k).

[sakshigupta]

I think this solution will take O(N^2 logK) Time complexity.

[praveenkesarwani]

Well what's the use of "sorted" term here if we have to insert all the elements in heap??

[hennadiikasian]

Wow. That was easy. I had troubles by doing the same with Python (we don't have max heap, and need to convert values to make it works).

[lostgen]

Very nice explanation. But i'm a little bit confused. We are doing binary search on values rather than indices. So how does this algorithm make sure that whatever we return at the end, low/high exists in the matrix?

[suryasingh]

hey, can we not do it more efficiently, since you have not used the extra info given i.e. the matrix is sorted row wise and column wise?