Kth Smallest Element in a Sorted Matrix

Time Complexity :-The counter function is O(n) and binary search is log(max_val-min_val). Hence, the time complexity is is O(n*log(max - min))

[abhinavpandey]

What iis the time complexity for this?

[surajrao]

Seen few videos above and wasn't satisfied, but this video reallly helped mainly due to the examples, thnx

[cppvideos]

supper video, keep uploading more videos on youtube

[hoyinli]

thx very much!
finally i understand the binary search method of this question!

[manjunathm]

Clear explanation, easy to understand thanks

[ayusharora]

Nice explanation. I watched 3 trending videos before this. But, they only showed 1 explanation. this had 2 examples, which gave a better understanding.

[avinash-xhqw]

Very nice explanation, how do we confirm that the value mid is present in the matrix

[aadeshsharma]

we should use the fact that each row is sorted while finding number of elements less than mid

[singha]

how are we ensuring that ans we get (when l==h satisfies) will present in the matrix?

[yolopassion]

It really helped me to understand this question.
Would be better if you could share the code link as well !!

[rohitshirur]

sir, I think we have to store mid value and do h = mid - 1 or else it will give time limit error in gfg


Code:
low = mat[0][0]
high = mat[n-1][n-1]
ans = -1
while low <= high:
mid = (low + high) // 2
res = count(mid, n, mat)
if res >= k:
ans = mid
high = mid-1
else:
low = mid + 1
return ans

[adrikagupta]

When the 'count' comes out to be our required count then why do we assume that the answer will be equal to or less than mid?
Eg: In the first sum, when mid was 14 what if there was a number X greater than mid but its count is also the required one and it lies in the matrix (not related to the first problem 'cause I know after 14 we have 15 which is the greatest).

[shivamsharma-oign]

It is giving TLE in [[-5, -4], [-5, -4]], k=2 case

[shravankhar]

its complexity will be O(n*log(n))? as counter function takes log n time ?

[tanmaybarman]

I think you should apply the binary search for counting also.

[priyadarshanr]

Is it necessary to pass "k" as a parameter to the counter function?

[anishsuman]

I have always a doubt how to insure that answer will lie in matrix but now I got to know how are we ensuring that if that is not in matrix in next iteration it will be replaced

[atlephuoc]

Can you explain why counter function take O(n) complexity in more detail ? Thanks !

[abhayphanse]

if i use mid = low+high/2 , it goes TLE for input [ [-5, -4], [-5, -4] ] and k=2 can anybody explain that

[swapnildhiman]

You can use upper_count also in your counter function.
But nice explanation