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 th-cam.com/video/FOa55B9Ikfg/w-d-xo.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.
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
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.
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 ?
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!
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 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!
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.
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
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.
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.....
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, 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"?
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)
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 :)
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.
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.
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.
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 :)
Great explanation, thanks so much. But why it is " row: i / totalColumns; col: i % totalColumns" at 8:17 of this video while " row in 2D matrix: 1DIndex / totalRows ; col in 2D matrix: 1DIndex % totalColumns" in github ? I'm so confused.
may be a mistake not sure, I think I saw a pr about this. maybe I merged a bad pr? no idea, I don't tend to the code base too well because I don't have the time. If you want to send a pr I'll merge it, otherwise I'm unable to look into this
Hi! What if I have scenario-2 matrix where I need to count the appearances of an X I am looking for? Matrix kind of like that: 1 4 8 2 8 11 8 10 15 I need to find how may times, 8 appears in the matrix. Thanks!
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.
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)) ?
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.
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 th-cam.com/video/FOa55B9Ikfg/w-d-xo.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
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.
"Reducing the search space..." - such a nice insight! Thanks man your lessons made me more confident.
nice.
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 😀
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
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.
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!
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.
The solution feels effortless once I have been through your videos! Thanks so much! :)
sure
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
I’m glad I found your TH-cam channel last night cuz I’ve been stuck on this problem for a while lol. 🙏🏾
welcome
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
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 😀
Of course it's helpful, you can influence lots of people and they benefited from your instructions. Keep it up, bro!
I will.
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
The king is so good at this I wonder where he gets his knowledge!!! I swear this is the best class anyone can take
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
The best algorithms guy in youtube, thank you!
This is spectacular! So clear and concise - bonus it covers the variant too!
I don't know why I didn't find your channel sooner. Thank you so much for this explanation!!
sure
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
Awesome !!. I think, today I understood both the approaches in depth. Won't forget now. :). Keep up the good work.
thx
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
Really appreciate how much effort this man takes to explain everything easily
thanks
Hey can you provide the code for this
Valuable tutorial, thanks! Where's the coding solution? It was mentioned in the description but I didn't find it.
Best explanation I ever heard. You taught to help us build mental model. You are awesome
thx
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 🤣
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
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 😀
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 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
The second variant was asked in Amazon coding test
Nice
This channel will be real big one day.
You deserve lot more views on your videos!
thx
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.....
thanks
Excellent elaboration! It is systematic and a easy to climb learning curve.
nice
You are just amazing Ben ! Thanks for covering both the variants !
Hi Ben, please keep going on, you will change the industry soon. Thank you very much for your efforts.
ok
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
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"?
Amazing!. You explained the detail thought process.
thanks
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
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.
you are great man , really doing good job , i paused the video in between to comment this
nice
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.
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.
You are doing great man. Keep it up!
ok
always helpful in my LeetCode learning!!!!!!!!!!!!!!!!!!!!!!!
Great to hear - we want to create something better than Leetcode one day
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/ 🎉
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
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
great explanation! very clear
thankls
@@BackToBackSWE just when i thought you had a bot making all these replies. lol
Thanks for the videos as always . You’re the man
sure
Great explanation, thanks so much. But why it is " row: i / totalColumns; col: i % totalColumns" at 8:17 of this video while " row in 2D matrix: 1DIndex / totalRows
; col in 2D matrix: 1DIndex % totalColumns" in github ? I'm so confused.
may be a mistake not sure, I think I saw a pr about this. maybe I merged a bad pr? no idea, I don't tend to the code base too well because I don't have the time. If you want to send a pr I'll merge it, otherwise I'm unable to look into this
@@BackToBackSWE ok, I'll send the pr later.
@@LeoKnight1986 thanks!
Hi!
What if I have scenario-2 matrix where I need to count the appearances of an X I am looking for?
Matrix kind of like that:
1 4 8
2 8 11
8 10 15
I need to find how may times, 8 appears in the matrix.
Thanks!
I'm not sure - I don't remember this video much
Back To Back SWE thanks I found a solution !
Awesome explanation!
thx
Thanks for the great explanation as always!
sure
Your explanation is amazing. Thanks
thanks
Great explanation! Thank you!
such an informative video. thanks boss
sure
God-level explanation!
You are the Best Sir ! Thank you so much
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
Brilliant Explaination 👍🏻
Excellent content!
thanks
Amazing!! Can't be better.
thanks.
Thanks a lot for your teaching!
Sure, it's nothing
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!
Great explanation man!
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.
Grt grt grt video.. Grt thinking power
thanks haha
Thank you so much for this video!
Thank you!
sure
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)) ?
Love you man...You are the best
no u
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*
As always, awesome content
best explanation ever seen:)
thx
I wish I could like the video more than once!
lol
super explaination!!! keep up the work, thanks :-)
ok. thanks.
beautiful explanation
Awesome!
Really appreciate it bro!
sure
really enjoy this video！
thx
very detailed lecture. Thanks for the content
sure
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
Awesome explanation. btw the code link is not working
got it
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.
where can i see the code?
The repository is deprecated - we only maintain backtobackswe.com now.
AWESOME! Thank you. Just subscribed ;)
sure thanks and nice
really helpful!!! thank you