Table of Contents: The Problem Introduction (Variant 1) 0:00 - 1:51 Jumping To The Brute Force 1:51 - 2:52 Optimizing Our Search 2:52 - 4:14 We Need To Notice Something... 4:14 - 5:49 The Data Does Not Dictate How We Interpret It 5:49 - 7:28 Establishing Our Mapping System 7:28 - 11:03 Executing The Binary Search 11:03 - 15:10 Runtime of Our Binary Search 15:10 - 15:45 The Problem Introduction (Variant 2) 15:45 - 16:43 Jumping To The Brute Force 16:43 - 17:15 The #1 Key To Search Problems 17:15 - 19:08 Defining Our Fundamental Decision Operation 19:08 - 20:57 Searching For Places To Start Our Search 20:57 - 22:48 Search Example #1 (Bottom Left Starting Point) 22:48 - 24:37 Search Example #2 (Top Right Starting Point) 24:37 - 25:38 What Just Happened 25:38 - 26:19 Analyzing Our Incremental Approach 26:19 - 28:34 Wrap Up 28:34 - 29:11 The code for both variants is in the description, fully commented for understanding purposes.
At ruclips.net/video/FOa55B9Ikfg/видео.html the complexity is between O(n) and O(log(n)), because the real "n" is n*m and using binary search on each row will be faster than O(n), where n are all numbers.
Haven't commented on a coding explanation video before but this is actually the best channel ever. I was struggling so hard with this problem until this video and this made everything seem so easy. Thank you so much, please never stop creating this amazing content.
Oh man!!! You are awesome!!! Lots people can write perfect code but not many of them can express their ideas and especially make others understand the code and why write the code this way.. but you MADE IT!!!! "Reducing the search space." You are genius!!! Thanks for all your hard working!!!
It took so much time for me to find someone on youtube like you who can explain in so much depth. There are lots of channels who explains the direct solutions but those are not really helping. You are the real hero who helps us to build the correct logic. Thank you so much. Keep making such good videos.
Whenever I can't understand any question and see that you have done a video on it already .. I feel so relieved!! Thanks for such awesome videos! Could you also make videos on how should we present the solution to questions asked in coding interviews ?
This channel has best explainations, the way he approaches, starts from brute-force, slowly move to optimal with clearly explaining each move, makes coding feel very easy. Love the contents. plz dont't stop, keep making the videos, of-course this channel can become the world's largest swe resource.
dude I have read many tutorials and discussions on this question but no one has actually explained why we choose top right or bottom left like you did. you're just awesome man
Keep doing what you're doing... please. You're so clear on explanations and without showing me code, I'm understanding the concepts of these questions so much more now. I wish I stumbled on these sooner. I'm actively applying right now as a graduating senior. I am not having much luck landing interviews due in part to my lack of an internship... but I'm hoping going through these practices will help me slam dunk whatever interview comes my way some day. Thank you!
You are a really awesome man:). I was afraid of these problems before, but once you explained the logic, I am so much confident now. If you continue to teach like this, no one can stop you from being the world's largest and best software engineering resource.
Carry on, bro. Your algo video is really different and effective than the other guys on the youtube. Others just give the solution but you are the one who tries to explain the reasons behind the solution.
The last bit is genius! I figured I can't reduce my search space when I started at the top left, but it just didn't strike me that the top right or bottom left would work.
The most beautiful and all-encompassing explanation of this problem solving approach on the internet! :) Your videos help a lot! Please keep up the good work Ben!
Hey, I've been watching your videos and they're very helpful for studying for interviews. You do some really clever things that I won't have thought of and I appreciated opening my perspective. Granted these problems weren't be done while I'm working at a SWE job but to get that job these types of videos are needed. Much love and best wishes in the future
Something that everyone seems to be missing that makes this problem a lot easier is that arrays and vectors are contiguous in memory. This means that you can just increment, so if there is 4 columns and you are at row 1, the index 4 (the start of the second row) can be accessed by simply doing array[4]. Just continue this from 0 to n*m. Much easier than messing around with the modulus and division.
Wow! Thank you for the easier method of solving the variant... I think at one point I understood the more complicated solution... but I have already forgot... and there is no way its going to come to me during high pressure interview... This method is very intuitive!
Hey what's up! I actually just got past the HC at Google! I spent about 5 weeks almost exclusively studying your videos (and Tushar Roy's along with some others) and doing Leetcode problems (I actually had that much time), and went onto my onsite and did pretty well. I pulled off the design interview, but would love to see a video or two on Software Design Interviews. Thanks again!
NICE! Wait...so you got hired? Or is there another step past hiring committee? I'm not fully familiar with the final steps. Also, check back in a little...I have plans...I'm launching a Patreon and have more announcements.
@@BackToBackSWE HC is pretty much hired they told me. They are just looking for a team placement. I think it varies from person to person though whether HC is the last step, but they indicated for me it was the last as far as problem s solving is concerned. Anywho, I'm still super into your stuff and will keep following it. I think I'm going to do competetivel coding as a hobby! You've really inspired me!
@@remyb9937 Nice! I was considering that route (competitive programming), but I don't think I'd be willing to dedicate the time to get really good...and I like talking better haha. Connect with me on LinkedIn if you want, let's stay in touch.
Hats off to ur explanation brother.. Beginners look for quick solutions and might skip ur vedio.. but believe me eventually they will follow u to learn the thought processs.....
Hey, thanks for the video. I came up with another solution that runs in log(m) + log(n) time. Don't know whether that's faster than log(mn). So the solution is - 1. We know each row is sorted. 2. We know each row is "contiguously" sorted, so that the last element of each row is less than or equal to the first element of the next row. 3. That means the first column would also be sorted. 4. So we do a binary search on just the first column. If the element is found, good; else, we can at least locate the row where the element would be. We just need to terminate our binary search when we get to a row where the first element is less than the element, and the next row's first element is greater than the element. This is log(m). 5. Then just do a binary search on this row. That's log(n). Think this works, but I'm not sure if that's faster than log(mn).
Yes, that sounds like a valid solution and is logarithmic. Edit (revising original answer): log(m) + log(n) is the same as log(m*n) by logarithm rules. Either way, both approaches are asymptotically the same.
Hey, really great explanation on exploiting the properties of a 2d matrix. One part I couldn't follow was at 14:21 , you calculate the midpoint at row 1 col 2. And the target value is greater than the midpoint. Did you mean to say "go to the right"?
YOU ARE GOD, buddy this channel is very very very impressive and your explanation skills are just over the top, i am sure i will see you in Google someday :)
As row heads are sorted as well, why dont u do binary search on Row heads to find out which exact row to search & then within that row u can do binary search. Assuming m rows & n columns, it can be done in O(log m) + O(log n)
Another great video even if I know the answer there is always something I missed or under thought in terms of a deeper exploration of the problem space.
Managed to do this one in O(n). :d 100% less memory than other users, but faster only than 5% of ppl on leetcode. Actually, I did the Search a 2D Matrix II.
i just saw it again. Do you think that the most optimal solution (the one that is so lengthy in CTCI) would be required to pass an intern internview? Cheers :)
For the second problem we could binary search each row or each column and get O(n * log m). We will definitely win in a situation if we have 1 x n or n x 1 matrix.
For the solution to the 1st variant: Why can't we find the required row in O(log(m)) and then search that row in O(log(n)) to make the total time complexity to search an element be O( log(m) + log(n) ) which is smaller that O(log(mn)) ?
Table of Contents:
The Problem Introduction (Variant 1) 0:00 - 1:51
Jumping To The Brute Force 1:51 - 2:52
Optimizing Our Search 2:52 - 4:14
We Need To Notice Something... 4:14 - 5:49
The Data Does Not Dictate How We Interpret It 5:49 - 7:28
Establishing Our Mapping System 7:28 - 11:03
Executing The Binary Search 11:03 - 15:10
Runtime of Our Binary Search 15:10 - 15:45
The Problem Introduction (Variant 2) 15:45 - 16:43
Jumping To The Brute Force 16:43 - 17:15
The #1 Key To Search Problems 17:15 - 19:08
Defining Our Fundamental Decision Operation 19:08 - 20:57
Searching For Places To Start Our Search 20:57 - 22:48
Search Example #1 (Bottom Left Starting Point) 22:48 - 24:37
Search Example #2 (Top Right Starting Point) 24:37 - 25:38
What Just Happened 25:38 - 26:19
Analyzing Our Incremental Approach 26:19 - 28:34
Wrap Up 28:34 - 29:11
The code for both variants is in the description, fully commented for understanding purposes.
At ruclips.net/video/FOa55B9Ikfg/видео.html the complexity is between O(n) and O(log(n)), because the real "n" is n*m and using binary search on each row will be faster than O(n), where n are all numbers.
I don't remember this video well enough to have a comment
Hi! I can't seem to locate the code
As a beginner, this channel is such a goldmine. The way you explain complex topics in a easy intuitive way is really amazing wow man
Thank you! Please enjoy a special code from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=madmax 🎉
Just got my FB swe intern offer yesterday! Your vids help out a ton man.
I will have my FB interview next week. Is it ok if I send a message to you?
@@darod6098 go for it
@@yusefmustafa2603 youtu.be/addme/-QH9AgDdeiTXzl3HYqC3bGJdfw4zYQ
nice, good job :) keep it up
Hey Yusef! Can I connect with you!? I am applying to FB as well within 3 weeks and i need some guidance!
Haven't commented on a coding explanation video before but this is actually the best channel ever. I was struggling so hard with this problem until this video and this made everything seem so easy. Thank you so much, please never stop creating this amazing content.
Oh man!!! You are awesome!!! Lots people can write perfect code but not many of them can express their ideas and especially make others understand the code and why write the code this way.. but you MADE IT!!!! "Reducing the search space." You are genius!!! Thanks for all your hard working!!!
thanks haha
Astounded this has < 10k views. By far the best content on these topics I've come across. Keep grinding Ben!
say no more
He has a magic of explaining dsa problems very well.
thanks
"Reducing the search space..." - such a nice insight! Thanks man your lessons made me more confident.
nice.
It took so much time for me to find someone on youtube like you who can explain in so much depth. There are lots of channels who explains the direct solutions but those are not really helping. You are the real hero who helps us to build the correct logic.
Thank you so much. Keep making such good videos.
Whenever I can't understand any question and see that you have done a video on it already .. I feel so relieved!! Thanks for such awesome videos!
Could you also make videos on how should we present the solution to questions asked in coding interviews ?
great - sure - I can't due to time constraints but we have backtobackswe.com (paywall)
Same, makes learning fun!
This channel has best explainations, the way he approaches, starts from brute-force, slowly move to optimal with clearly explaining each move, makes coding feel very easy. Love the contents. plz dont't stop, keep making the videos, of-course this channel can become the world's largest swe resource.
dude I have read many tutorials and discussions on this question but no one has actually explained why we choose top right or bottom left like you did. you're just awesome man
no u
The solution feels effortless once I have been through your videos! Thanks so much! :)
sure
Keep doing what you're doing... please. You're so clear on explanations and without showing me code, I'm understanding the concepts of these questions so much more now. I wish I stumbled on these sooner. I'm actively applying right now as a graduating senior. I am not having much luck landing interviews due in part to my lack of an internship... but I'm hoping going through these practices will help me slam dunk whatever interview comes my way some day. Thank you!
Hahahaha. Yes. This project is still very much active (as long as people demonstrate interest). We will continue to expand.
You are a really awesome man:). I was afraid of these problems before, but once you explained the logic, I am so much confident now. If you continue to teach like this, no one can stop you from being the world's largest and best software engineering resource.
ye, lez do it
Carry on, bro. Your algo video is really different and effective than the other guys on the youtube. Others just give the solution but you are the one who tries to explain the reasons behind the solution.
ok - carrying on
Just stumbled upon this video and have to say youre one of the best teachers for computer science I have seen.
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
The second variant was asked in Amazon coding test
Nice
Of course it's helpful, you can influence lots of people and they benefited from your instructions. Keep it up, bro!
I will.
The last bit is genius! I figured I can't reduce my search space when I started at the top left, but it just didn't strike me that the top right or bottom left would work.
nice
This is spectacular! So clear and concise - bonus it covers the variant too!
The best algorithms guy in youtube, thank you!
I’m glad I found your RUclips channel last night cuz I’ve been stuck on this problem for a while lol. 🙏🏾
welcome
The king is so good at this I wonder where he gets his knowledge!!! I swear this is the best class anyone can take
The most beautiful and all-encompassing explanation of this problem solving approach on the internet! :) Your videos help a lot! Please keep up the good work Ben!
nice yo
Sir,
Your videos are AWESOME , nothing can be better than this!!! ...
could you please do some videos on system design problems.....
yeah, we will find someone for that
Hey, I've been watching your videos and they're very helpful for studying for interviews. You do some really clever things that I won't have thought of and I appreciated opening my perspective. Granted these problems weren't be done while I'm working at a SWE job but to get that job these types of videos are needed. Much love and best wishes in the future
Sure
I don't know why I didn't find your channel sooner. Thank you so much for this explanation!!
sure
One of the best explanations or walkthroughs I have ever seen for any problem.
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Really appreciate how much effort this man takes to explain everything easily
thanks
Hey can you provide the code for this
I've literally stopped doing office work this corona season. I log in, finish stand-up and come here :P This is fascinating stuff !!
great
Best explanation I ever heard. You taught to help us build mental model. You are awesome
thx
Valuable tutorial, thanks! Where's the coding solution? It was mentioned in the description but I didn't find it.
awesome as always. Best spent 29 minutes of the day ! Do a video on spiral matrix.
hahahaha, sure. And I only take suggestions from Patrons who support the project now. To be fair to those paying to support the project
You deserve lot more views on your videos!
thx
Been watching your vids and got my Amazon interview next week. Hopefully goes well!
2 people messaged me and said they got in Amazon after peeping the vids...you got this :)
@@BackToBackSWE Just got my offer. Thanks a bunch man, keep up the great work!
@@JG-zu6nq nice, good luck at your new job!
Awesome !!. I think, today I understood both the approaches in depth. Won't forget now. :). Keep up the good work.
thx
This channel will be real big one day.
This video is the most genius video ever! Super super good buddy!! we love u!!!
no love u go internet
@@BackToBackSWE what r u talking about buddy 🤣
Something that everyone seems to be missing that makes this problem a lot easier is that arrays and vectors are contiguous in memory. This means that you can just increment, so if there is 4 columns and you are at row 1, the index 4 (the start of the second row) can be accessed by simply doing array[4]. Just continue this from 0 to n*m. Much easier than messing around with the modulus and division.
Excellent elaboration! It is systematic and a easy to climb learning curve.
nice
Wow! Thank you for the easier method of solving the variant... I think at one point I understood the more complicated solution... but I have already forgot... and there is no way its going to come to me during high pressure interview... This method is very intuitive!
sure
No one could explain it better than you
thanks
I like your emphasis on the fundamentals. The fundamentals!
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Hey what's up! I actually just got past the HC at Google! I spent about 5 weeks almost exclusively studying your videos (and Tushar Roy's along with some others) and doing Leetcode problems (I actually had that much time), and went onto my onsite and did pretty well. I pulled off the design interview, but would love to see a video or two on Software Design Interviews. Thanks again!
NICE! Wait...so you got hired? Or is there another step past hiring committee? I'm not fully familiar with the final steps.
Also, check back in a little...I have plans...I'm launching a Patreon and have more announcements.
@@BackToBackSWE HC is pretty much hired they told me. They are just looking for a team placement. I think it varies from person to person though whether HC is the last step, but they indicated for me it was the last as far as problem s solving is concerned. Anywho, I'm still super into your stuff and will keep following it. I think I'm going to do competetivel coding as a hobby! You've really inspired me!
@@remyb9937 Nice! I was considering that route (competitive programming), but I don't think I'd be willing to dedicate the time to get really good...and I like talking better haha.
Connect with me on LinkedIn if you want, let's stay in touch.
Hi Ben, please keep going on, you will change the industry soon. Thank you very much for your efforts.
ok
You are just amazing Ben ! Thanks for covering both the variants !
Amazing!. You explained the detail thought process.
thanks
always helpful in my LeetCode learning!!!!!!!!!!!!!!!!!!!!!!!
Great to hear - we want to create something better than Leetcode one day
Hats off to ur explanation brother..
Beginners look for quick solutions and might skip ur vedio.. but believe me eventually they will follow u to learn the thought processs.....
thanks
Hey, thanks for the video. I came up with another solution that runs in log(m) + log(n) time. Don't know whether that's faster than log(mn).
So the solution is -
1. We know each row is sorted.
2. We know each row is "contiguously" sorted, so that the last element of each row is less than or equal to the first element of the next row.
3. That means the first column would also be sorted.
4. So we do a binary search on just the first column. If the element is found, good; else, we can at least locate the row where the element would be. We just need to terminate our binary search when we get to a row where the first element is less than the element, and the next row's first element is greater than the element. This is log(m).
5. Then just do a binary search on this row. That's log(n).
Think this works, but I'm not sure if that's faster than log(mn).
Yes, that sounds like a valid solution and is logarithmic.
Edit (revising original answer): log(m) + log(n) is the same as log(m*n) by logarithm rules. Either way, both approaches are asymptotically the same.
@@BackToBackSWE Thanks! Your videos are a boon, by the way.
@@BarneyBing883 nice
Your videos are really awesome!
Thanks for helping!
sure - flourish
you are great man , really doing good job , i paused the video in between to comment this
nice
Awesome explanation!
thx
Hey, really great explanation on exploiting the properties of a 2d matrix. One part I couldn't follow was at 14:21 , you calculate the midpoint at row 1 col 2. And the target value is greater than the midpoint. Did you mean to say "go to the right"?
You are doing great man. Keep it up!
ok
Thanks for the videos as always . You’re the man
sure
YOU ARE GOD, buddy this channel is very very very impressive and your explanation skills are just over the top, i am sure i will see you in Google someday :)
thanks ha.
God-level explanation!
great explanation! very clear
thankls
@@BackToBackSWE just when i thought you had a bot making all these replies. lol
As row heads are sorted as well, why dont u do binary search on Row heads to find out which exact row to search & then within that row u can do binary search. Assuming m rows & n columns, it can be done in O(log m) + O(log n)
im not sure I dont remember this problem's details too well
Great explanation! Thank you!
Amazing!! Can't be better.
thanks.
Thanks for the great explanation as always!
sure
Subscribed in first 10 seconds. Amazing content.
Thanks, appreciate it 😄 We'd love for you to check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉
Brilliant Explaination 👍🏻
Your explanation is amazing. Thanks
thanks
Grt grt grt video.. Grt thinking power
thanks haha
such an informative video. thanks boss
sure
Another great video even if I know the answer there is always something I missed or under thought in terms of a deeper exploration of the problem space.
Nice.... Really enjoying this... Your presentation has improved... Keep up the good work.
I know.
Excellent content!
thanks
You are the Best Sir ! Thank you so much
Great explanation man!
thanks
best explanation ever seen:)
thx
Thanks a lot for your teaching!
Sure, it's nothing
beautiful explanation
As always, awesome content
Thank you so much for this video!
Awesome!
Really appreciate it bro!
sure
12:03 We need to do our Math: opens the marker cap. Nah the animation guy will take care of it XD. Btw awesome video bud as always!
I wish I could like the video more than once!
lol
Managed to do this one in O(n). :d 100% less memory than other users, but faster only than 5% of ppl on leetcode.
Actually, I did the Search a 2D Matrix II.
nice
@@BackToBackSWE You know what else is nice ? Your channel! Keep up the good work mate.
@@ЏонМастерман thx
Love you man...You are the best
no u
Bestest explanation ⚡🎉🎈🎈😀
yoyo
really enjoy this video！
thx
Thank you!
sure
very detailed lecture. Thanks for the content
sure
super explaination!!! keep up the work, thanks :-)
ok. thanks.
I've really liked your way of explaining
It would be of great help to me if you create videos on system design
Please
I will eventually, I am not an expert in that so I need to learn first before I can authoritatively teach that. It is in high demand amongst people.
really helpful!!! thank you
Let's make it more challenging. In the second variant, instead of directly searching for an element, find the kth smallest/largest element.
ok
Sounds like basic chemistry, bro
i just saw it again. Do you think that the most optimal solution (the one that is so lengthy in CTCI) would be required to pass an intern internview?
Cheers :)
Not sure it really depends
I would say it is about where we can build heuristic function (11 corners) and where we can not(other corners). And everything goes similar to A*
For the second problem we could binary search each row or each column and get O(n * log m).
We will definitely win in a situation if we have 1 x n or n x 1 matrix.
For the solution to the 1st variant: Why can't we find the required row in O(log(m)) and then search that row in O(log(n)) to make the total time complexity to search an element be O( log(m) + log(n) ) which is smaller that O(log(mn)) ?
You are amazing and really like your video.
thanks
A video a day keeps your ignorance away : great job uncle :)
ok....son
23:19 it only gets worse...nice line
wut
AWESOME! Thank you. Just subscribed ;)
sure thanks and nice