Maximum Sum Rectangle In A 2D Matrix - Kadane's Algorithm Applications (Dynamic Programming)
Вставка
- Опубліковано 19 вер 2024
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Given a 2D matrix with integer values (and including at least 1 positive value) find the sub-rectangle with the largest sum.
I want to step you through all of the tough mental leaps to solve this problem.
Complexities
Let rows = the number of rows
Let cols = the number of columns
Naive Runtime: Ω(rows^2 * cols^2)
Explanation:
There are rows * cols possible start points and for each rows * cols possible start points we will do O(rows * cols) work, this causes us to have our time lower bounded by the amount of time it takes to explore all top left and bottom right combinations so that we can explore all 2D rectangles in the matrix.
This is not even including getting the sum for each 2D rectangle we set bounds for (we can do it in O(rows).
Similar to this problem leetcode.com/p...
Optimal Solution Runtime (2D Kadane's): O(cols^2 * rows)
We will try all combinations of left and right ending points for the possible 2D rectangle.
For that O(col^2) work we will do O(row) work to run Kadane's on the row sum cache (for each left-right combination of the possible final rectangle).
So the cumulative work will be O(cols^2 * rows).
Space will be O(rows) because of the vertical rows sum cache.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
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
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? :-)
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
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...
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.
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!
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 UA-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?😂
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
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
your subscription should grow 10 times more, your teaching is clear and easy-to-understand, concise as gold.
thanks haha
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
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
One of best explanation available online.
thx
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.
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
I love the passion you are trying to explain and it's all crystal clear. Love your channel, good job mate!
nice, thx
Clear explanations! Thank you so much!
sure
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.
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
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
man start taking system design topics as well .. u explain really well
thanks
Very underrated channel...Amazing videos
thanks
This explanation was very helpful and clear. You have a natural talent for teaching.
Thanks for the clear explanation, love that you paced the video really well
thx
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
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
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
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
Bro just keep up the good work. The approach of solving the problems is really great.
thanks
best tutorial of the question
thx
We need more people like you. Big thank from Vietnam!
i literally never look at the code as the explanation itself is soo good.
nice!
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.
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
awesome interpretation. Excellent job!
thx
Best DSA channel on the planet!
Damn! I Love you man! Such crystal clear explanations!
thx
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.
Dude i wanna thanks you clear explanation and you really put work in ! and subscribed hope you keep posting algorthime problems
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
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! A hard problem turned into an easy problem now
Great explanation!!!!!
sure!
Like and comment-done
Prerequisites done for watching video ;)
great ha
omg such a fantastic explanation.....hats off man.
thanks
one of the best explanation i came so far
could not have got any better ...!
nailed it ..!!
THanks
The brute force time complexity is O(row^3* col^3).
This video is so great, really made the hard problem easy to understand.
nice
Thanks for your clear explaination !!!
sure
thanks man that was a great explanation
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
Very genuine and i love the way you explain.. it leverages the thought process which really matters rather memorising!!!!
Thanks for your explanation!
NIce explanation! Thank you so much!
awesome explanation !!!!
your video is good,
gfg article does not explain the solution to this question properly.
thx
So much helpful.Thank you .
but you are not decrementing top left point, so how come you are checking each of the possible rectangle sum in DP approach ?
Wonderful! Thanks for putting in all the effort!
DRY run is awesome!
Excellent video. Thanks!
sure
Wow, ThankYou. You rock.
thanks
"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 - ua-cam.com/video/ZMOFmHBVEcg/v-deo.html
i would say this is the best explanation I found so far, thank you for sharing!
It turned out awesome ♥️
Thanks for this kind of explanation!
Dude, you are the best
thanks.
another amazing explanation
thx
Nicely explained
thanks
Hats Off dude. Gr8 way of explanation Tushar Roy can learn a thing or two from you
hahahahaha ok
I think we could also do prefix sum on rows to do sums faster
I would like to meet you and thanks for this special video...I was like wooowww
Hahaa thanks buddy!
I don't think your code will work when all entries are negative as your kadanae function returns values greater than or equal to zero.
if you substitute by this it should do fine.
public int maxSubArray(int[] nums) {
int maxEndingHere=0;
int max=Integer.MIN_VALUE;
int cS=0,cE=0;
int gS=-1,gE=-1;
for(int i=0;imaxEndingHere+nums[i]){
cS=i;cE=i;
maxEndingHere=nums[i];
}else{
cE=i;
maxEndingHere=maxEndingHere+nums[i];
}
if(maxEndingHere>max){
gS=cS;gE=cE;
max=maxEndingHere;
}
}
System.out.print(gS+" "+gE);
return max;
}
great explanation btw.
yeah it won't work with negatives
Bruhhhhhh... you're awesome!! Totally loved the you taught. Thanks much for this video!!
code is not in the description.
but anyways video is excellent.
The repository is deprecated - we only maintain backtobackswe.com now.
your content is great. Thank you
thx
You are amazing.TYSM
sure!
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
You are the best bro !
thx
HEY JOHN LEGEND>>NICE WORK BUDDY>>YOU ARE A GREAT SINGER INDEED
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.
Great video
I wish we can meet someday. Thank you for your efforts !!
sure
Great work dude! Nice one :-)
Thanks
Sorry where is the code? Great video, it helped me so much!
Nice explanation
hey
You were right.. tushar was missing why kadane was used
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Thank u, u are incredible
sure
Damn you reply to every single comment, also the new setup is quite good.
yes, I do. and thx
u are awsome man!
thanks
wonderful explanatrion
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.
absolutely awesome
best explaination bro