Kth Smallest Element in a Sorted Matrix | Algorithm Explanation by alGOds

In this video, Vaibhav has explained the solution to a #Popular Interview Question #KthSmallestElementInASortedMatrix in O(n*log(MaxVal)) time complexity.
Question Link: leetcode.com/problems/kth-sma...
Feel free to ask any of your doubts and discuss your attempts related to this question in the comments section 😇.
Join this telegram channel for regular updates : t.me/alGOdsCZcams
Join this telegram group for doubts and discussions : t.me/joinchat/PqjeMhz0MBR-tg3...
Do like and subscribe to our channel and click the bell icon so you don’t miss any future videos!!.
Don’t forget to tell us about the Questions you need an explanatory video for in the comments section. We’ll definitely take care of it😁.
Here is the Subscription Link : / algods99
Connect with us on Gmail : [e-mail]
The contributors to this channel and their profile links are enlisted below
1) Vishesh Aggarwal:
LinkedIn :- / vishesh-aggarwal-830b5...
2) Vaibhav Varshney:
LinkedIn :- / vaibhav-varshney
3) Vagish Yagnik:
LinkedIn :- / vagish-yagnik-9203b0172
4) Vishesh Jain:
LinkedIn :- / vishesh-jain-138097174
5) Achint Dawra:
LinkedIn :- / achint-dawra-ba9550168
6) V Sriram:
LinkedIn :- / sriram-v-08b098170
7) Varun Bajlotra:
LinkedIn :- / varun-bajlotra-17715a170
8) Vikas Yadav:
LinkedIn :- / vikas-yadav-b432b5107

[@alGOds99]

Join this telegram channel for regular updates : t.me/alGOdsCZcams
Join this telegram channel for doubts and discussions : t.me/joinchat/PqjeMhz0MBR-tg31OK2Dsg

[@abhimanyushekhawat2626]

Thanks bro for this intuition. Saved me a lot of time.

[@JaiPrakash-ku7it]

I didn't get it. It is too difficult to get for a beginner. Please explain its code if possible.

[@bluemeet8546]

very nice explaination i am struggling with this quetion since a week but we can also use upperbound function to calculate the number of elements which are smaller than k by iterating over rows

[@_cytosine]

Thank you for the video. Just some minor comment: When discussing complexity, I'd always simplify the classes just to avoid confusion when you are comparing different algorithms with similar complexities. For example, at 2:06, I'd rather say O(n^2 log n).

[@anushanshayadav2015]

Keep it up. Going very well👍👍

[@alGOds99]

Thank You!!😁😄

[@bluemeet8546]

you are really god of algos keep continuing this good work

[@pogo7052]

Wonderful explanation!

[@pqazx1]

Plz solve using heaps as well..

[@decostarkumar2562]

Excellent 👌

[@yashagarwal9425]

Omg, You made it so simple... I was stuck with this for 3 days, solved it in 10 mins

[@piyushjhaGeek]

(low+high)/2 is subject to overflow. Use low + (high-low)/2 OR high - (high-low)/2

[@Sunny-ri4yo]

Hey! how will this solution handle the case when suppose mid is 4 (4 isn't in the matrix) and number of elements less than 4 comes out to be required then we have to decrease the high bound, but what if answer was actually 5 (which was actually present in the matrix) but we will never check for 5.

[@rutujapatil5355]

Same Doubt

[@bhaveshhmc2634]

In that case, we won't change the low variable but assign mid-value to the high and we go for another iteration to check the same count is occurring or not if it does then the previous count value is not the correct one!

[@bhaveshhmc2634]

you can go to this link for a better explanation czcams.com/video/dpsp1hP6P-U/video.html

[@sharmaak8039]

Veryyyy well explained ✨🔥

[@alGOds99]

Thank You😁😇

[@bhuwaneshnainwal8323]

Thanks

[@alGOds99]

Glad to help:)

[@Prashantkumar-pn6qq]

Hi, Can you explain this(08:45) a bit more, please?

[@yy-qx9lx]

bro from where did you learn this algorithm?

[@alGOds99]

This algorithm is a mixture of two algos.
There's no exact source available to learn this algorithm.
It comes from practice and intuition :)

[@donnsharma9490]

Educative.io course grokking the coding the interview is the source or go to the Leetcode discuss there you will get nicer explanation of this question

[@sulaimant5690]

czcams.com/video/oeQlc87HbbQ/video.html

[@blasttrash]

he copied it from leetcode. if he did not copy he would explained the so called "intuition", but no, he jumps straight into algorithm which is a clear indication that he didn't come up with this on his own.

[@janvimahajan8447]

Awesome explanation!

[@alGOds99]

Glad you liked it :)

[@prajeshbandhubanerjee357]

Need of count ??

[@insane2539]

Why during dry run you applying binary search on the elements instead of the index of the elements, is there any specific reason?

[@SiddyMta]

At 2:10 why do we need to sort the array? why can't we just iterate the matrix with two loops and print the value at k-1. This will give us O(n^2) complexity right?

[@Cube2deth]

Maybe the matrix will have
1 2 3
4 5 8
7 8 9
See the 7 will come after 8 in your soluitino (the last element of previous row might no be bigger than first element of next row:D

[@AmazingWorld-fw9oc]

Count function explanation is not good plzz give more details about it.

[@abhishekjha2182]

It was difficult to understand but great work 😃

[@SHASHIKUMAR-pp4hg]

good for nothing,why you cannot simply return a[(k-1)/c][(k-1)%c]

[@satishmhetre5301]

Doesn't work for the following matrix
1 4 7
2 5 8
3 6 9
Now for 4th element using your formula we get, a[(4-1)/3][(4-1)%3] = a[1][0] = 2. Which is obviously not the correct answer.

[@utkarshgupta2909]

@@satishmhetre5301 sorted matrix means 123 456 789.. otherwise the author would not have mentioned first method to push them in array and choose arr[k-1] out of that

[@satishmhetre7117]

Matrix given by me is row wise sorted.

[@utkarshgupta2909]

@@satishmhetre7117 then this approach won't work

[@bhavnasoni9148]

int solve(int mat[][c], int r, int c, int k){
int min = mat[0][0], max = mat[c-1][c-1];
int desired = k;
while(min < max){
int mid = min+(max-min)/2;
int place = 0;
for(int i=0; i

[@sukshithshetty8349]

didnt understand

[@AmazingWorld-fw9oc]

this tutorial was not helpful at all, please give a better explanation from next time.

[@ankurkumar8465]

Your approach is a bit wrong.

[@willturner3440]

Mere se bhi dislike le le bhai

[@saeedmirzaei1]

Very bad explanation although this solution is a good one...