Table of Contents: Geekin' 0:00 - 0:16 Going Meta 0:16 - 1:08 The Problem Introduction 1:08 - 2:47 Beginning of Brute Force Walkthrough 2:47 - 5:17 We Try The Next Top Left Planting 5:17 - 5:57 Analyzing The Brute Force's Runtime 5:57 - 6:33 Bounding The Work In Choosing Bottom Right Corners 6:33 - 7:31 Deriving A Lower Bound For The Brute Force 7:31 - 8:51 The Lower Bound For The Brute Force 8:51 - 9:38 Can We Do Better? 9:38 - 9:43 Beginning The Optimal Solution Walkthrough 9:43 - 10:18 Explaining The Algorithm 10:18 - 12:26 How Do We Pick An Optimal Top & Bottom For The Max Rectangle? 12:26 - 14:28 Walkthrough Continues 14:28 - 20:22 We Find The Best Rectangle 20:22 - 21:19 Walkthrough Continues 21:19 - 22:55 Recapping What Just Happened 22:55 - 23:50 Deriving The Optimal Solution Time Complexity 23:50 - 25:38 Space Complexity 25:38 - 26:07 Wrap Up 26:07 - 26:46 Mistakes: 11:17 -> The entry at index 3 in the runningRowSums array should be -8, not 8. Sorry. Yeah, the LED light is reflecting sharply off my glasses, I'll get something to diffuse the light better next time. The code for this problem is in the description. Fully commented for teaching purposes.
This is such a smart and beautiful application of Kadane's algorithm. And explained so patiently and I'm such detailed manner, it was pure bliss to watch. Thank you for making such videos.
if you are watching this in lockdown you are one of the rare species on the earth . many students are wasting their time on facebook, youtube, twitter, netflix, watching movies playing pubg, but you are working hard to achieve something . ALL the best ...nitj student here
Normally, I skip videos that explain a concept in more than 10 minutes as usually they talk a lot but say very little. I’m glad I stayed for the long haul on this one Lol Excellent explanation. You speak clearly, make pauses, and do not leave anything to chance. Thank you! Ps- I don’t recommend starting your videos with those 2 guys goofing around. For the people who come across your channel for the very first time (such as me right now), this is a very good way to send off potential viewers. I almost gave up until you appeared.
I do not remember a single word I said in this video whatsoever, glad it helped. And yeah, I am fully aware of this phenomenon, these older videos were around when no one watched.
Your channel has one of the best explanations for every question. The way you describe the thought process behind and cover everything from brute force to explaining about complexities makes it way easier to understand. Thanks a lot!
Thank you so much for putting out these videos! You explain the thought process of coming up with the answer (arguably the most important part of the process; converting to code is usually quite easy once you understand the problem) way, way better than any other channel I've come across. Tiny mistake I noticed: at 13:00, the last entry of running sum should be -8, not 8. This threw me off a little when you said 6 was the largest contiguous subarray.
Great job! A nit to help others: In the running row sum for the first col when L = R= 0 at 14:00, the last row in the blue array has 8 while the original matrix has -8. Confuses why 6 is the largest when compared to 8, if you're caught off-guard! :-)
initially i thought this would be the same as Tushar Roy's tutorial vid, turns out it wasn't! the good part is you really added more to what was already explained by Tushar, great job!
I've been sitting trying to solve this as my algorithm assignment and all I could get after 5 hours of staring was the brute force solution. This opened my "third" eye. :D Great videos, thank you very much
I've been here watchin you almost an year now, I've literally recommended your channel to everyone at my college NIT Jalandhar, one of the colleges of National Importance in India. We love you bro, your're the best thing that could have ever happened to RUclips!
So true. I'm binging these videos rn to study for my algorithms exam next week. I'm feeling better since I'm actually starting to understand dynamic programming. Thank you!
What a clear and awesome explanation. The meat of the video starts at 10 min mark. That's where the row sum array is introduced. Left, Right, Top, Bottom and running row sum is what's needed Anytime we are trying to solve a 2D sum problem we need to check continuous sum of a 1D array ( the row sum in this example). In brief anytime we have an 'N' dimensional structure we will need to look at (N-1) running sum structure.
@@BackToBackSWE hi... I'm a final year undergrad student preparing for interview. And B2B_SWE is the best place because of its in-depth analysis of the problems and solutions is much needed to develop problem solving ability... Thanks man. By the way, where are you from, USA?
I have a question. If we knew that N or M is bigger. Would it help to transpose the matrix so that there are less running row sums to compute? If so, would the speedup be significant? My guess would be that it would make sense for matrices that have M >> N. Also it appears, that we would only save on space complexity, not time complexity in particular.
Best explaination so far. Im going to watch the whole playlist in sequence. Im really enjoying it. 😮🙌 Why not sort the playlist on the basis of difficulty for people watching in sequence.. ✌️
Great explanation on this one! Coming up with a solution and coding it up in 45 minutes seems unreasonable. Hoping people aren't actually being asked this in interviews!
okay but what if the max contiguous subarray sum is present more than once, and is also greater than the max rectangle sum so far? what do we do then? (situation that occurs in 15:28)
I have a quick modification questions. If we wanted to find squares instead of rectangles, how would you approach this problem? I am not able to figure that out
Similar to rectangle but only restriction is instead of kadane,you need to find max subarray of size K( K = R-L+1) in the sum column. This can also be done in o(m) time,so complexity is same.
For Time Complexity - Since we are finding all pairs of cols, that makes it O(cols^2). And with in each pair, we will do sequential passes over rows right? One pass to add new elements to update running row sum and the other pass to find max using Kadane's algorithm. That makes the passes as O(2*rows). Since 2 is constant, the final TC becomes O(cols^2 * rows). Is this right? Writing this just for clarification.
![I.N "HALLUCINATION" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/n5B5q1Hwt_U/mqdefault.jpg)
Table of Contents:
Geekin' 0:00 - 0:16
Going Meta 0:16 - 1:08
The Problem Introduction 1:08 - 2:47
Beginning of Brute Force Walkthrough 2:47 - 5:17
We Try The Next Top Left Planting 5:17 - 5:57
Analyzing The Brute Force's Runtime 5:57 - 6:33
Bounding The Work In Choosing Bottom Right Corners 6:33 - 7:31
Deriving A Lower Bound For The Brute Force 7:31 - 8:51
The Lower Bound For The Brute Force 8:51 - 9:38
Can We Do Better? 9:38 - 9:43
Beginning The Optimal Solution Walkthrough 9:43 - 10:18
Explaining The Algorithm 10:18 - 12:26
How Do We Pick An Optimal Top & Bottom For The Max Rectangle? 12:26 - 14:28
Walkthrough Continues 14:28 - 20:22
We Find The Best Rectangle 20:22 - 21:19
Walkthrough Continues 21:19 - 22:55
Recapping What Just Happened 22:55 - 23:50
Deriving The Optimal Solution Time Complexity 23:50 - 25:38
Space Complexity 25:38 - 26:07
Wrap Up 26:07 - 26:46
Mistakes:
11:17 -> The entry at index 3 in the runningRowSums array should be -8, not 8. Sorry.
Yeah, the LED light is reflecting sharply off my glasses, I'll get something to diffuse the light better next time.
The code for this problem is in the description. Fully commented for teaching purposes.
Hello bro I don't find any description?
It was a good effort thankyou.
The repository is deprecated, we only maintain backtobackswe.com now.
@@BackToBackSWE This code is not even there in backtobackswe premium member access. Could you plz provide?
@Back To Back SWE i couldnt find code there as well
Buddy the way you explain makes brute-force also look awesome 😂😂 You are the best teacher!
sure fam
The Thought process is what i needed. Thank You .
sure
This is such a smart and beautiful application of Kadane's algorithm. And explained so patiently and I'm such detailed manner, it was pure bliss to watch. Thank you for making such videos.
thanks.
you good with code
you are no fraud
explain very well
Knowledgeable as hell
thanks
@@BackToBackSWE that's a poem haha
Is writing Haikus your 'thing',
Mr Jaskaran Singh? :-)
if you are watching this in lockdown you are one of the rare species on the earth . many students are wasting their time on facebook, youtube, twitter, netflix, watching movies playing pubg, but you are working hard to achieve something . ALL the best ...nitj student here
an inspiration
Bro yahi tune tushar roy ke video me bhi likha hai naa 😜
@@mradulagrawal1579 😂😂😂😂
why there is even a need to tell from which college u are...
Normally, I skip videos that explain a concept in more than 10 minutes as usually they talk a lot but say very little. I’m glad I stayed for the long haul on this one Lol
Excellent explanation. You speak clearly, make pauses, and do not leave anything to chance. Thank you!
Ps- I don’t recommend starting your videos with those 2 guys goofing around. For the people who come across your channel for the very first time (such as me right now), this is a very good way to send off potential viewers. I almost gave up until you appeared.
I do not remember a single word I said in this video whatsoever, glad it helped. And yeah, I am fully aware of this phenomenon, these older videos were around when no one watched.
Your channel has one of the best explanations for every question. The way you describe the thought process behind and cover everything from brute force to explaining about complexities makes it way easier to understand. Thanks a lot!
thanks and sure!
You made my day, I saw so many posts and videos none of them explained why we are doing.
I have been following you since 2019
Thank you so much for putting out these videos! You explain the thought process of coming up with the answer (arguably the most important part of the process; converting to code is usually quite easy once you understand the problem) way, way better than any other channel I've come across.
Tiny mistake I noticed: at 13:00, the last entry of running sum should be -8, not 8. This threw me off a little when you said 6 was the largest contiguous subarray.
Thank you, and got it, I updated the teacher's notes.
One of best explanation available online.
thx
Great job! A nit to help others: In the running row sum for the first col when L = R= 0 at 14:00, the last row in the blue array has 8 while the original matrix has -8. Confuses why 6 is the largest when compared to 8, if you're caught off-guard! :-)
thanks
I love the passion you are trying to explain and it's all crystal clear. Love your channel, good job mate!
nice, thx
Best explanation I have ever found
thanks, hey
You did a really good job by explaining what Tushar didn't. Finally understood this problem pretty well !
ye
Thanks for uploading this. One of the best explanation I have came across. Keep up the good work.
hey
@@BackToBackSWE hello
@@jishulayek8252 hi, this is Ben. hey
your subscription should grow 10 times more, your teaching is clear and easy-to-understand, concise as gold.
thanks haha
We need more people like you. Big thank from Vietnam!
LOved it bro.... this content deserves to be paid. clear,concise set of words and what not.
thanks - and it is we have backtobackswe.com
initially i thought this would be the same as Tushar Roy's tutorial vid, turns out it wasn't! the good part is you really added more to what was already explained by Tushar, great job!
thanks
Best DSA channel on the planet!
I've been sitting trying to solve this as my algorithm assignment and all I could get after 5 hours of staring was the brute force solution. This opened my "third" eye. :D Great videos, thank you very much
great
I've been here watchin you almost an year now, I've literally recommended your channel to everyone at my college NIT Jalandhar, one of the colleges of National Importance in India. We love you bro, your're the best thing that could have ever happened to RUclips!
thanks and nice, and haha thanks
Lol why the flex though? NIT Jalandhar is a shit tier 2 college no company even cares about to visit.
"NIT Jalandhar, one of the colleges of National Importance in India" , one question, Why?😂
This explanation was very helpful and clear. You have a natural talent for teaching.
Wow thanks man. You explain so good that it's not even necessary to see the code for implementing 👌👏
aw thx
So true. I'm binging these videos rn to study for my algorithms exam next week. I'm feeling better since I'm actually starting to understand dynamic programming. Thank you!
@@maripaz5650 nice
Bro just keep up the good work. The approach of solving the problems is really great.
thanks
thank you, implementing the algorithm felt so soft after your explanation, keep up
ye
What a clear and awesome explanation. The meat of the video starts at 10 min mark. That's where the row sum array is introduced. Left, Right, Top, Bottom and running row sum is what's needed
Anytime we are trying to solve a 2D sum problem we need to check continuous sum of a 1D array ( the row sum in this example). In brief anytime we have an 'N' dimensional structure we will need to look at (N-1) running sum structure.
Very underrated channel...Amazing videos
thanks
Thanks for the clear explanation, love that you paced the video really well
thx
i literally never look at the code as the explanation itself is soo good.
nice!
man start taking system design topics as well .. u explain really well
thanks
Really good videos. I am prepping for coding interviews and I guess this is one of the best resources that one can go through.
ye
where u got the placement
Clear explanations! Thank you so much!
sure
Very genuine and i love the way you explain.. it leverages the thought process which really matters rather memorising!!!!
I just hit the gold-mine of Coding..... This is priceless... I'm very very thankful to the B2B_SWE guys...
lol hi
@@BackToBackSWE hi... I'm a final year undergrad student preparing for interview. And B2B_SWE is the best place because of its in-depth analysis of the problems and solutions is much needed to develop problem solving ability... Thanks man. By the way, where are you from, USA?
@@debayondharchowdhury2680 sure and yes the united states
your explanation is soooooo CLEAR and THOROUGH and you INDEED help me. Thank you for your sharing. :)
thanks and great
explanation is brilliant ,wow it seems so easy when u explained,great job,please keep doing this
thanks and great
Dude, you are the best
thanks.
awesome interpretation. Excellent job!
thx
Dude i wanna thanks you clear explanation and you really put work in ! and subscribed hope you keep posting algorthime problems
best tutorial of the question
thx
one of the best explanation i came so far
omg such a fantastic explanation.....hats off man.
thanks
could not have got any better ...!
nailed it ..!!
THanks
Damn! I Love you man! Such crystal clear explanations!
thx
This video is so great, really made the hard problem easy to understand.
nice
Was looking for the thought process for a similar problem. Found gold.
great
dude, you are just fab with explanation's and time complexity
I try to be as fab as possible.
I have a question. If we knew that N or M is bigger. Would it help to transpose the matrix so that there are less running row sums to compute? If so, would the speedup be significant? My guess would be that it would make sense for matrices that have M >> N. Also it appears, that we would only save on space complexity, not time complexity in particular.
it says the code in the description, where is the description ? Thank you for your amazing explanation . This is the best I've heard .
The repository is deprecated - we only maintain backtobackswe.com now. and thanks
@@BackToBackSWE Thank you
Best video I have ever seen from u and also it's good that u are telling the time complexity at the end of video
ye
i would say this is the best explanation I found so far, thank you for sharing!
Wonderful! Thanks for putting in all the effort!
Best explaination so far. Im going to watch the whole playlist in sequence. Im really enjoying it. 😮🙌
Why not sort the playlist on the basis of difficulty for people watching in sequence.. ✌️
ha, never considered it, may do so
Wow! A hard problem turned into an easy problem now
Great explanation!!!!!
sure!
but you are not decrementing top left point, so how come you are checking each of the possible rectangle sum in DP approach ?
Thanks for your clear explaination !!!
sure
Thanks for your explanation!
It turned out awesome ♥️
another amazing explanation
thx
Bruhhhhhh... you're awesome!! Totally loved the you taught. Thanks much for this video!!
Great explanation on this one! Coming up with a solution and coding it up in 45 minutes seems unreasonable. Hoping people aren't actually being asked this in interviews!
yes
I got it. It fucked me up.
Wow, ThankYou. You rock.
thanks
NIce explanation! Thank you so much!
thanks man that was a great explanation
Thanks for this kind of explanation!
So much helpful.Thank you .
okay but what if the max contiguous subarray sum is present more than once, and is also greater than the max rectangle sum so far? what do we do then? (situation that occurs in 15:28)
I don't remember the contents of this video and am fast replying to comments :/
awesome explanation !!!!
You are the best bro !
thx
Excellent video. Thanks!
sure
DRY run is awesome!
Nicely explained
thanks
You are amazing.TYSM
sure!
where is the code ??????
The repository is deprecated - we only maintain backtobackswe.com now.
your content is great. Thank you
thx
Thank u, u are incredible
sure
Hats Off dude. Gr8 way of explanation Tushar Roy can learn a thing or two from you
hahahahaha ok
Thank you so much man. You made it crystal clear. Really appreciate your efforts.
where is the code in the description?
The repository is deprecated, we only maintain backtobackswe.com now.
Thanks for the explanation, where is the code for this algorithm? I can't find it
Nice explanation
hey
your video is good,
gfg article does not explain the solution to this question properly.
thx
I have a quick modification questions.
If we wanted to find squares instead of rectangles, how would you approach this problem?
I am not able to figure that out
im not sure dont remember tbh
Similar to rectangle but only restriction is instead of kadane,you need to find max subarray of size K( K = R-L+1) in the sum column. This can also be done in o(m) time,so complexity is same.
Great work dude! Nice one :-)
Thanks
HEY JOHN LEGEND>>NICE WORK BUDDY>>YOU ARE A GREAT SINGER INDEED
Can we use recursion in this. ??
code is not in the description.
but anyways video is excellent.
The repository is deprecated - we only maintain backtobackswe.com now.
Sorry where is the code? Great video, it helped me so much!
Brilliant!! Thanks"
absolutely awesome
For Time Complexity -
Since we are finding all pairs of cols, that makes it O(cols^2). And with in each pair, we will do sequential passes over rows right? One pass to add new elements to update running row sum and the other pass to find max using Kadane's algorithm. That makes the passes as O(2*rows). Since 2 is constant, the final TC becomes O(cols^2 * rows). Is this right?
Writing this just for clarification.
wonderful explanatrion
thx
u are awsome man!
thanks
best explaination bro
Great video
The brute force time complexity is O(row^3* col^3).
Like and comment-done
Prerequisites done for watching video ;)
great ha
Legend 🙏🏻🧠🧠🧠