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

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

[@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...

[@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? :-)

[@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.

[@suraj8087]

The Thought process is what i needed. Thank You .

[@BackToBackSWE]

sure

[@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.

[@AyushKarn25]

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

[@BackToBackSWE]

ye

[@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!

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

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

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

[@kartaLaLa]

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

[@BackToBackSWE]

thanks haha

[@VaibhavJain]

One of best explanation available online.

[@BackToBackSWE]

thx

[@grabsmench]

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

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

[@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.

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

[@tom0313choi]

Best explanation I have ever found

[@BackToBackSWE]

thanks, hey

[@lemonginger001]

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

[@BackToBackSWE]

thanks

[@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.

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

[@adithyabhat4770]

Very underrated channel...Amazing videos

[@BackToBackSWE]

thanks

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

[@JasonKT13]

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

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

[@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.

[@wishfulthinker6139]

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

[@BackToBackSWE]

nice!

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

[@r2123b]

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

[@BackToBackSWE]

thanks and great

[@lizziedaffofil6064]

Best DSA channel on the planet!

[@lucysmith9039]

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

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

[@kshitijagrawal2648]

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

[@BackToBackSWE]

thanks

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

[@Chesstreamer]

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

[@BackToBackSWE]

thanks and great

[@shobhitkumar6820]

best tutorial of the question

[@BackToBackSWE]

thx

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

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

[@maharajak6578]

one of the best explanation i came so far

[@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!

[@loudarck2402]

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

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

[@hullyoung]

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

[@BackToBackSWE]

thx

[@AmberK296]

Clear explanations! Thank you so much!

[@BackToBackSWE]

sure

[@dikshantyadav1110]

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

[@BackToBackSWE]

I try to be as fab as possible.

[@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.

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

[@premkumarsubbiah2972]

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

[@vanshajsingh6314]

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

[@BackToBackSWE]

thx

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

[@yaosongding1479]

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

[@BackToBackSWE]

nice

[@ankitgoyal8556]

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

[@BackToBackSWE]

great ha

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

[@j.c9858]

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

[@schu649]

awesome interpretation. Excellent job!

[@BackToBackSWE]

thx

[@qingli8466]

Thanks for your explanation!

[@vaibhavchauhan7179]

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

[@BackToBackSWE]

thanks

[@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.

[@user-gz9tb1kc3y]

NIce explanation! Thank you so much!

[@ritikagupta8847]

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

[@shubhamjindal9214]

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

[@BackToBackSWE]

THanks

[@ManishSharma-fi2vr]

DRY run is awesome!

[@roinskitty]

thanks man that was a great explanation

[@naveenmeena1832]

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

[@BackToBackSWE]

hahahahaha ok

[@nutanchavan5464]

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

[@isaaczhanbaev3655]

Dude, you are the best

[@BackToBackSWE]

thanks.

[@yutaitadori7318]

It turned out awesome ♥️

[@VIJAYKUMAR-tn1kr]

So much helpful.Thank you .

[@Ritikjain9211]

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

[@BackToBackSWE]

thx

[@shishirkakhandki9230]

Wonderful! Thanks for putting in all the effort!

[@VipinKumar-us1sr]

I would like to meet you and thanks for this special video...I was like wooowww

[@BackToBackSWE]

Hahaa thanks buddy!

[@AnhLe-hc8qm]

Thanks for your clear explaination !!!

[@BackToBackSWE]

sure

[@Junaid.K]

code is not in the description. but anyways video is excellent.

[@BackToBackSWE]

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

[@LegitGamer2345]

awesome explanation !!!!

[@adityasrivastava7956]

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

[@shivamjalotra7919]

Wow, ThankYou. You rock.

[@BackToBackSWE]

thanks

[@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.

[@shivarammuthukumaraswamy7164]

You are amazing.TYSM

[@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 :/

[@sebastianvillamil9319]

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

[@AnshMehtaGR8]

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

[@BackToBackSWE]

yes, I do. and thx

[@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.

[@varunagarwal5189]

another amazing explanation

[@BackToBackSWE]

thx

[@ManishSharma-fi2vr]

Thanks for this kind of explanation!

[@sumana_19]

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

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

[@zivashnivash2512]

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

[@kanishkmavi1220]

best explaination bro

[@abhishekmahapatra4323]

where is the code in the description?

[@BackToBackSWE]

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

[@SuperCoolDudeVideo]

absolutely awesome

[@puperhacker2150]

Excellent video. Thanks!

[@BackToBackSWE]

sure

[@Ayushkumar-xj9vl]

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

[@BackToBackSWE]

sure

[@lifeofMani97]

You are the best bro !

[@BackToBackSWE]

thx

[@janpoonthong]

Great video

[@abhigupta6681]

your content is great. Thank you

[@BackToBackSWE]

thx

[@maripaz5650]

wonderful explanatrion

[@BackToBackSWE]

thx

[@olicmoon]

Nicely explained

[@BackToBackSWE]

thanks

[@BelalMoawadOfficial]

Thank u, u are incredible

[@BackToBackSWE]

sure