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

📹 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).

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.

++++++++++++++++++++++++++++++++++++++++++++++++++

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

[abhinavsingh]

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

[suraj]

The Thought process is what i needed. Thank You .

[mayukhchanda]

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.

[Official-tknc]

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

[IamSinghJaskaran]

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

[pratibhashrivastav]

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!

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

[VishalKumar-krme]

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

[AyushKarn]

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

[kartaLaLa]

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

[srinaath]

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

[lucysmith]

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

[favs]

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!

[arsalankhalid]

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.

[bldbld]

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

[JasonKT]

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

[anuragpateriya]

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

[dominikcl]

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

[adithyabhat]

Very underrated channel...Amazing videos