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-s...
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
Watch video Maximum Sum Rectangle In A 2D Matrix - Kadane's Algorithm Applications (Dynamic Programming) online without registration, duration hours minute second in high quality. This video was added by user Back To Back SWE 06 February 2019, don't forget to share it with your friends and acquaintances, it has been viewed on our site 77,450 once and liked it 2.5 thousand people.