Maximum Sum Rectangle In A 2D Matrix - Kadane's Algorithm Applications (Dynamic Programming)

[@BackToBackSWE]

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.

[@Happy-on2is]

Hello bro I don't find any description? It was a good effort thankyou.

[@BackToBackSWE]

The repository is deprecated, we only maintain backtobackswe.com now.

[@niteshkhetan9757]

@@BackToBackSWE This code is not even there in backtobackswe premium member access. Could you plz provide?

[@bakiyalak1993]

@Back To Back SWE i couldnt find code there as well

[@Official-tk3nc]

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

[@BackToBackSWE]

an inspiration

[@mradulagrawal1579]

Bro yahi tune tushar roy ke video me bhi likha hai naa 😜

[@vend57]

@@mradulagrawal1579 😂😂😂😂

[@vanshsehgal9475]

why there is even a need to tell from which college u are...

[@mayukhchanda5805]

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.

[@BackToBackSWE]

thanks.

[@wirito]

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.

[@BackToBackSWE]

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.

[@abhinavsingh4221]

Buddy the way you explain makes brute-force also look awesome 😂😂 You are the best teacher!

[@BackToBackSWE]

sure fam

[@IamSinghJaskaran]

you good with code you are no fraud explain very well Knowledgeable as hell

[@BackToBackSWE]

thanks

[@conorhynes8633]

@@BackToBackSWE that's a poem haha

[@0anant0]

Is writing Haikus your 'thing', Mr Jaskaran Singh? :-)

[@suraj8087]

The Thought process is what i needed. Thank You .

[@BackToBackSWE]

sure

[@VishalKumar-kr9me]

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

[@pratibhashrivastav5770]

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!

[@BackToBackSWE]

thanks and sure!

[@Maholain]

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.

[@BackToBackSWE]

Thank you, and got it, I updated the teacher's notes.

[@AyushKarn25]

You did a really good job by explaining what Tushar didn't. Finally understood this problem pretty well !

[@BackToBackSWE]

ye

[@anandartwork]

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! :-)

[@BackToBackSWE]

thanks

[@kartaLaLa]

your subscription should grow 10 times more, your teaching is clear and easy-to-understand, concise as gold.

[@BackToBackSWE]

thanks haha

[@anuragpateriya787]

LOved it bro.... this content deserves to be paid. clear,concise set of words and what not.

[@BackToBackSWE]

thanks - and it is we have backtobackswe.com

[@jishulayek8252]

Thanks for uploading this. One of the best explanation I have came across. Keep up the good work.

[@BackToBackSWE]

hey

[@jishulayek8252]

@@BackToBackSWE hello

[@BackToBackSWE]

@@jishulayek8252 hi, this is Ben. hey

[@bldbld18]

I love the passion you are trying to explain and it's all crystal clear. Love your channel, good job mate!

[@BackToBackSWE]

nice, thx

[@arsalankhalid8170]

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.

[@grabsmench]

We need more people like you. Big thank from Vietnam!

[@dominikcl1]

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

[@BackToBackSWE]

great

[@adamyamishra9179]

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 KZbin!

[@BackToBackSWE]

thanks and nice, and haha thanks

[@jaideepmanhas6034]

Lol why the flex though? NIT Jalandhar is a shit tier 2 college no company even cares about to visit.

[@mizanali9529]

"NIT Jalandhar, one of the colleges of National Importance in India" , one question, Why?😂

[@VaibhavJain]

One of best explanation available online.

[@BackToBackSWE]

thx

[@favs5286]

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]

thanks

[@srinaath9845]

Wow thanks man. You explain so good that it's not even necessary to see the code for implementing 👌👏

[@BackToBackSWE]

aw thx

[@maripaz5650]

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!

[@BackToBackSWE]

@@maripaz5650 nice

[@lucysmith9039]

This explanation was very helpful and clear. You have a natural talent for teaching.

[@kshitijagrawal2648]

Bro just keep up the good work. The approach of solving the problems is really great.

[@BackToBackSWE]

thanks

[@tom0313choi]

Best explanation I have ever found

[@BackToBackSWE]

thanks, hey

[@arijitabanerjee9579]

Really good videos. I am prepping for coding interviews and I guess this is one of the best resources that one can go through.

[@BackToBackSWE]

ye

[@consistentprani5034]

where u got the placement

[@dominikcl1]

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.

[@JasonKT13]

thank you, implementing the algorithm felt so soft after your explanation, keep up

[@BackToBackSWE]

ye

[@lizziedaffofil6064]

Best DSA channel on the planet!

[@wishfulthinker6139]

i literally never look at the code as the explanation itself is soo good.

[@BackToBackSWE]

nice!

[@debayondharchowdhury2680]

I just hit the gold-mine of Coding..... This is priceless... I'm very very thankful to the B2B_SWE guys...

[@BackToBackSWE]

lol hi

[@debayondharchowdhury2680]

@@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?

[@BackToBackSWE]

@@debayondharchowdhury2680 sure and yes the united states

[@adithyabhat4770]

Very underrated channel...Amazing videos

[@BackToBackSWE]

thanks

[@Chesstreamer]

explanation is brilliant ,wow it seems so easy when u explained,great job,please keep doing this

[@BackToBackSWE]

thanks and great

[@premkumarsubbiah2972]

Very genuine and i love the way you explain.. it leverages the thought process which really matters rather memorising!!!!

[@hullyoung]

Thanks for the clear explanation, love that you paced the video really well

[@BackToBackSWE]

thx

[@lemonginger001]

man start taking system design topics as well .. u explain really well

[@BackToBackSWE]

thanks

[@r2123b]

your explanation is soooooo CLEAR and THOROUGH and you INDEED help me. Thank you for your sharing. :)

[@BackToBackSWE]

thanks and great

[@loudarck2402]

Dude i wanna thanks you clear explanation and you really put work in ! and subscribed hope you keep posting algorthime problems

[@harifrahman8054]

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

[@BackToBackSWE]

ye

[@heyitsnikhil7956]

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.. ✌️

[@BackToBackSWE]

ha, never considered it, may do so

[@yaosongding1479]

This video is so great, really made the hard problem easy to understand.

[@BackToBackSWE]

nice

[@j.c9858]

i would say this is the best explanation I found so far, thank you for sharing!

[@Od253]

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!

[@BackToBackSWE]

yes

[@ASD-tg4zu]

I got it. It fucked me up.

[@utkarsh_goel]

Was looking for the thought process for a similar problem. Found gold.

[@BackToBackSWE]

great

[@tanujabharti8043]

Wow! A hard problem turned into an easy problem now Great explanation!!!!!

[@BackToBackSWE]

sure!

[@maharajak6578]

one of the best explanation i came so far

[@dikshantyadav1110]

dude, you are just fab with explanation's and time complexity

[@BackToBackSWE]

I try to be as fab as possible.

[@AmberK296]

Clear explanations! Thank you so much!

[@BackToBackSWE]

sure

[@lotsalearn]

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)

[@BackToBackSWE]

I don't remember the contents of this video and am fast replying to comments :/

[@vanshajsingh6314]

Damn! I Love you man! Such crystal clear explanations!

[@BackToBackSWE]

thx

[@vaibhavchauhan7179]

omg such a fantastic explanation.....hats off man.

[@BackToBackSWE]

thanks

[@nutanchavan5464]

Bruhhhhhh... you're awesome!! Totally loved the you taught. Thanks much for this video!!

[@shubhamjindal9214]

could not have got any better ...! nailed it ..!!

[@BackToBackSWE]

THanks

[@isaaczhanbaev3655]

Dude, you are the best

[@BackToBackSWE]

thanks.

[@shishirkakhandki9230]

Wonderful! Thanks for putting in all the effort!

[@shobhitkumar6820]

best tutorial of the question

[@BackToBackSWE]

thx

[@schu649]

awesome interpretation. Excellent job!

[@BackToBackSWE]

thx

[@wanwan6234]

it says the code in the description, where is the description ? Thank you for your amazing explanation . This is the best I've heard .

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now. and thanks

[@wanwan6234]

@@BackToBackSWE Thank you

[@aalekhsrivastava9973]

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.

[@Mohit-cn2us]

but you are not decrementing top left point, so how come you are checking each of the possible rectangle sum in DP approach ?

[@naveenmeena1832]

Hats Off dude. Gr8 way of explanation Tushar Roy can learn a thing or two from you

[@BackToBackSWE]

hahahahaha ok

[@AnhLe-hc8qm]

Thanks for your clear explaination !!!

[@BackToBackSWE]

sure

[@qingli8466]

Thanks for your explanation!

[@roinskitty]

thanks man that was a great explanation

[@yutaitadori7318]

It turned out awesome ♥️

[@孫傅康]

NIce explanation! Thank you so much!

[@blackkiritok]

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

[@BackToBackSWE]

im not sure dont remember tbh

[@Jay-dm4id]

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.

[@oscaropdyou]

"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)?

[@BackToBackSWE]

I'm not sure don't remember the problem much

[@oscaropdyou]

@@BackToBackSWE I was referring to this - kzbin.info/www/bejne/kH6yd6B-d7t4mck

[@varunagarwal5189]

another amazing explanation

[@BackToBackSWE]

thx

[@ManishSharma-fi2vr]

Thanks for this kind of explanation!

[@lifeofMani97]

You are the best bro !

[@BackToBackSWE]

thx

[@sumana_19]

Thank you so much man. You made it crystal clear. Really appreciate your efforts.

[@VIJAYKUMAR-tn1kr]

So much helpful.Thank you .

[@adityasrivastava7956]

HEY JOHN LEGEND>>NICE WORK BUDDY>>YOU ARE A GREAT SINGER INDEED

[@LegitGamer2345]

awesome explanation !!!!

[@shivamjalotra7919]

Wow, ThankYou. You rock.

[@BackToBackSWE]

thanks

[@puperhacker2150]

Excellent video. Thanks!

[@BackToBackSWE]

sure

[@ketiperanidze8603]

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.

[@abhigupta6681]

your content is great. Thank you

[@BackToBackSWE]

thx

[@ManishSharma-fi2vr]

DRY run is awesome!

[@zivashnivash2512]

Thanks for the explanation, where is the code for this algorithm? I can't find it

[@marcousosewelle5501]

Great work dude! Nice one :-)

[@BackToBackSWE]

Thanks

[@olicmoon]

Nicely explained

[@BackToBackSWE]

thanks

[@Ritikjain9211]

your video is good, gfg article does not explain the solution to this question properly.

[@BackToBackSWE]

thx

[@Calisthenoob]

Hey, great explanation as always, and while I didn’t care much for the lighting, the 2 separate boards feels kinda odd to me.. Also, are you gonna do a graph boot camp similar to the one you did for the tree anytime soon? Would be a huge help!

[@BackToBackSWE]

I can do a graph video...it'll happen eventually. Really the core thing you need to understand about graphs is DFS and BFS which I covered a while back (kzbin.info/www/bejne/inrFhpiboNiLmas). Every acyclic connected graph is a tree, and all trees are acyclic connected graphs. Also, when you say "I didn’t care much for the lighting" does that indicate indifference to it or is it worse than other videos? And yeah understood, I will keep to 1 large board.

[@Calisthenoob]

@@BackToBackSWE I meant the lighting didn't make a difference to me.. Thanks for the link, i'll check it out!

[@BackToBackSWE]

@@Calisthenoob ok great

[@nhuquantcheng7112]

Thank you so much for your clear and intelligent explanation, it helped me a lot with my homework :D the best channel ever

[@BackToBackSWE]

Thank You!! Do check out backtobackswe.com/platform/content and please recommend us to your family and friends :)

[@ujjawaltyagi302]

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.

[@BackToBackSWE]

yeah it won't work with negatives

[@BelalMoawadOfficial]

Thank u, u are incredible

[@BackToBackSWE]

sure

[@SmokyBigSmoke]

You are amazing.TYSM

[@BackToBackSWE]

sure!

[@ankitgoyal8556]

Like and comment-done Prerequisites done for watching video ;)

[@BackToBackSWE]

great ha

[@sebastianvillamil9319]

Sorry where is the code? Great video, it helped me so much!

[@pranjlisingh6490]

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

[@BackToBackSWE]

ye

[@pranjlisingh6490]

@@BackToBackSWE will wait for the video...thanks

[@nemesis9410]

ummmm... that's great and all, but I don't see Dynamic Programming here. What's the semantic array? How do you reuse the solutions for smaller sub-problems?

[@BackToBackSWE]

I don't remember the solution/this video too much, refresh me

[@nemesis9410]

@@BackToBackSWE Hey! I was just looking to solve this problem using DP, but in your case you use Kadane's algorithm, which according to the internets is not considered DP by everyone (idk how that works tbh). What's I'm used to is defining a semantic array (similar to knapsack problems) and reusing array entries to reduce the problem to a subproblem. So I'm just asking if I missed any of that here?

[@Ayushkumar-xj9vl]

I wish we can meet someday. Thank you for your efforts !!

[@BackToBackSWE]

sure

[@AnshMehtaGR8]

Damn you reply to every single comment, also the new setup is quite good.

[@BackToBackSWE]

yes, I do. and thx

[@Epictetus777]

Can we use recursion in this. ??

[@bhavukgarg3619]

Nice explanation

[@BackToBackSWE]

hey

[@ritikagupta8847]

The brute force time complexity is O(row^3* col^3).

[@SuperCoolDudeVideo]

absolutely awesome