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.
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.
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.
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!
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 TH-cam!
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.
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
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!
@@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?
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! :-)
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.
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!
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.
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!
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.
"We will try all combinations of left and right ending points for the possible 2D rectangle." - Can we use range sum querying per row to reduce the time complexity to O(rows*cols)?
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.
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)
Nice Explanation !! But I thought Final Time complexity would be *Symmetric* with respect to Rows And Cols , But its Not 😶 "Strange " .... But Space complexity is O(rows)..... So Can I conclude That the Total Complexity(time and space) combined is Symmetrical ? Btw Awesome explanation :)
![ทุกครั้งที่หลับตา (Lucid Dream) - AYLA's [ Official MV ]](http://i.ytimg.com/vi/4i1OBAQyv58/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
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...
Buddy the way you explain makes brute-force also look awesome 😂😂 You are the best teacher!
sure fam
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? :-)
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.
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.
The Thought process is what i needed. Thank You .
sure
your subscription should grow 10 times more, your teaching is clear and easy-to-understand, concise as gold.
thanks haha
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 did a really good job by explaining what Tushar didn't. Finally understood this problem pretty well !
ye
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 TH-cam!
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?😂
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
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.
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
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
One of best explanation available online.
thx
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
Very underrated channel...Amazing videos
thanks
Best DSA channel on the planet!
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
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 literally never look at the code as the explanation itself is soo good.
nice!
Best explanation I have ever found
thanks, hey
This explanation was very helpful and clear. You have a natural talent for teaching.
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.
I love the passion you are trying to explain and it's all crystal clear. Love your channel, good job mate!
nice, thx
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
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
man start taking system design topics as well .. u explain really well
thanks
thank you, implementing the algorithm felt so soft after your explanation, keep up
ye
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.
Bro just keep up the good work. The approach of solving the problems is really great.
thanks
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
one of the best explanation i came so far
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
Very genuine and i love the way you explain.. it leverages the thought process which really matters rather memorising!!!!
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.
Thanks for the clear explanation, love that you paced the video really well
thx
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
Was looking for the thought process for a similar problem. Found gold.
great
Wow! A hard problem turned into an easy problem now
Great explanation!!!!!
sure!
i would say this is the best explanation I found so far, thank you for sharing!
but you are not decrementing top left point, so how come you are checking each of the possible rectangle sum in DP approach ?
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.
best tutorial of the question
thx
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
could not have got any better ...!
nailed it ..!!
THanks
This video is so great, really made the hard problem easy to understand.
nice
Clear explanations! Thank you so much!
sure
dude, you are just fab with explanation's and time complexity
I try to be as fab as possible.
Dude i wanna thanks you clear explanation and you really put work in ! and subscribed hope you keep posting algorthime problems
omg such a fantastic explanation.....hats off man.
thanks
awesome interpretation. Excellent job!
thx
"We will try all combinations of left and right ending points for the possible 2D rectangle." - Can we use range sum querying per row to reduce the time complexity to O(rows*cols)?
I'm not sure don't remember the problem much
@@BackToBackSWE I was referring to this - th-cam.com/video/ZMOFmHBVEcg/w-d-xo.html
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
DRY run is awesome!
Dude, you are the best
thanks.
Thanks for the explanation, where is the code for this algorithm? I can't find it
Thanks for your explanation!
The brute force time complexity is O(row^3* col^3).
Sorry where is the code? Great video, it helped me so much!
Damn! I Love you man! Such crystal clear explanations!
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.
It turned out awesome ♥️
another amazing explanation
thx
Bruhhhhhh... you're awesome!! Totally loved the you taught. Thanks much for this video!!
So the best time complexity we can get is o(n^3) (if rows and columns are both equal to n). I wonder if there is a better solution.
Thanks for your clear explaination !!!
sure
Can we use recursion in this. ??
NIce explanation! Thank you so much!
So much helpful.Thank you .
Hats Off dude. Gr8 way of explanation Tushar Roy can learn a thing or two from you
hahahahaha ok
thanks man that was a great explanation
Wonderful! Thanks for putting in all the effort!
your video is good,
gfg article does not explain the solution to this question properly.
thx
Thanks for this kind of explanation!
Like and comment-done
Prerequisites done for watching video ;)
great ha
HEY JOHN LEGEND>>NICE WORK BUDDY>>YOU ARE A GREAT SINGER INDEED
You are the best bro !
thx
Nicely explained
thanks
awesome explanation !!!!
You are amazing.TYSM
sure!
Wow, ThankYou. You rock.
thanks
code is not in the description.
but anyways video is excellent.
The repository is deprecated - we only maintain backtobackswe.com now.
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 :/
Excellent video. Thanks!
sure
I think we could also do prefix sum on rows to do sums faster
best explaination bro
Can't find this question on LC... what in the world is happening?
Thank u, u are incredible
sure
Nice Explanation !! But I thought Final Time complexity would be *Symmetric* with respect to Rows And Cols , But its Not 😶
"Strange " .... But Space complexity is O(rows).....
So Can I conclude That the Total Complexity(time and space) combined is Symmetrical ?
Btw Awesome explanation :)
I wish we can meet someday. Thank you for your efforts !!
sure
Nice explanation
hey
can u please make a video on how to find kth largest element in a row wise and column wise sorted matrix using binary search
ye
@@BackToBackSWE will wait for the video...thanks
Damn you reply to every single comment, also the new setup is quite good.
yes, I do. and thx
where is the code in the description?
The repository is deprecated, we only maintain backtobackswe.com now.
wonderful explanatrion
thx
your content is great. Thank you
thx