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

Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
? 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 https://leetcode.com/problems/range-sum-query-2d-immutable/


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: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww

Tuschar Roy: https://www.youtube.com/user/tusharroy2525

GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ

Jarvis Johnson: https://www.youtube.com/user/VSympathyV

Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw