[RUBRIK INTERVIEW QUESTION] Kth Smallest Number Multiplication Table | LeetCode | Solution Explained

668. Kth Smallest Number in Multiplication Table. I explain the binary search approach in detail. Solution coded in Python3.
Writeup (Summary + Code):
chaudhary1337.com/kth-smalles...
Problem link:
leetcode.com/problems/kth-sma...
==================================================
Timestamps:
0:18 Problem discussion
1:55 Bruteforce solution
3:31 Optimal solution
8:01 Binary search explanation
12:21 Code for Binary search
==================================================
Stuff I use:
My mic: amzn.to/3Fsx1Ok
My laptop: amzn.to/3oHfqw4
My headphones: amzn.to/3BrwTfI
My pen-tablet: amzn.to/3lCIZx6
NOTE: These are affiliate links.
- Doesn't cost you anything
- Gives me a kickback if you buy this
==================================================
Donate:
PayPal: paypal.me/chaudharytanishq
Buy Me a Coffee: www.buymeacoffee.com/chaudhar...
==================================================
Follow:
LeetCode: leetcode.com/chaudhary1337/
GitHub: github.com/chaudhary1337
LinkedIn: / tanishq-chaudhary-a203...
My Website: chaudhary1337.com/
My (old) Website: chaudhary1337.github.io/
#LeetCode #coding #programming #chaudhary1337
==================================================

[@chaudharycodes]

Summary, Code & Complexity Analysis present on the website, as usual.
chaudhary1337.com/kth-smallest-number-in-multiplication-table/

[@ahasunos5914]

Very calm and composed. You gained a subscriber.

[@G5Sahithireddy]

Very good explanation .Thank you

[@chriszeng1488]

Really good explanation. Please keep up the good work.

[@hoyinli7462]

u spent 2 hours making this video. really appreciate your work!

[@jaygujarathi7296]

Wonderful Explanation. Can't come up with such solution in first attempt. Well done man

[@chaudharycodes]

This problem is definitely on the trickier side

[@Yash-uk8ib]

@@chaudharycodes ya, I had some observations with the priority queue, u can clearly see that the repeated elements cannot be repeated more than two times.. Also there would be no.s which cannot come in between 1 to m*n, so I had no method to check no.s coming twice and also which are not in the range, so that soln was a complete waste...
This tar//i is something insane.
thanks for ur video

[@hoyinli7462]

great work!

[@4cooolbrooo471]

Clearly explained thanks for Google job offer

[@chaudharycodes]

Congratulations!

[@dinohunter7176]

I think I saw this solution slightly different on the solution tab xĐ , but you adapted for your own xD
Still I saw you understood the counting of divisors of middle, but not really on the why the counting is done, and why based on that is established the lower or higher limits for BS :)
Btw, for mid to avoid int buffer overflow I recommend
mid = lower + ( ( higher - lower ) / 2 )
if int is 2^31 - 1 , with mid = (higher +lower)/2 will get overflow
if lower is >= 1 and higher is 2^31-1
Still, this video has better explanation on the solution than many channels who copy paste without actually understanding... the goal is to understand the method even if it was created by someone else, later you could use the method to invent another optimized solution for another problem :)

[@kasturisanyal6649]

What a wonderful explanation ! Your technique to teach is awesome. Keep up the good work

[@ashirbad29]

Thanks Tanishq, wonderful explanation 🙌

[@sahilanower9189]

Hey Nice Explanation! And good intuition behind the algo at the first place of reducing search space and overshoot and undershoot.

[@sreejith5966]

Wow your explanation is so good 🔥

[@theghostwhowalk]

thanks for great explanation!

[@exextrovert2350]

wonderful explanation buddy!!!!!!!.

[@sandeepvaid4275]

Which whiteboard software you use for writing ?

[@chaudharycodes]

I use OneNote for visuals.

[@yevgendrachenko3655]

Isn't it enough to initialize lo and hi as 1 an m*n?

[@yasirmalik198]

Yes - It can be done that way too
class Solution(object):
def findKthNumber(self, m, n, k):
def enough(x):
count = 0
for i in range(1, m+1):
count += min(x // i, n)
return count >= k
lo, hi = 1, m * n
while lo < hi:
mi = (lo + hi) // 2
if not enough(mi):
lo = mi + 1
else:
hi = mi
return lo

[@chaudharycodes]

@@yasirmalik198 Thanks for sharing your code :)
@Yevgen Drachenko Yeah. I just realized right now, since the largest element in the matrix can only be m*n, and smallest 1, we can indeed initialize lo as 1 and hi as m*n. Thanks for asking :D

[@hoyinli7462]

1 feedback. Please draw more diagrams when explaining the tricks. Sometime it is quite hard to follow just by words. eg. @9:39, maybe just my opinion, it's still not very clear why binary search can be used in this case.

[@chaudharycodes]

Ah I see, will definitely spend more time creating visuals. Thanks for the feedback :D