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
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching
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
Видео Maximum Sum Rectangle In A 2D Matrix - Kadane's Algorithm Applications (Dynamic Programming) канала Back To Back SWE
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching
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
Видео Maximum Sum Rectangle In A 2D Matrix - Kadane's Algorithm Applications (Dynamic Programming) канала Back To Back SWE
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
![Max Contiguous Subarray Sum - Cubic Time To Kadane's Algorithm ("Maximum Subarray" on LeetCode)](https://i.ytimg.com/vi/2MmGzdiKR9Y/default.jpg)
![](https://i.ytimg.com/vi/7yC1aN87Ydo/default.jpg)
![Longest Common Subsequence (2 Strings) - Dynamic Programming & Competing Subproblems](https://i.ytimg.com/vi/ASoaQq66foQ/default.jpg)
![Largest rectangle in Histogram | Leetcode #84](https://i.ytimg.com/vi/vcv3REtIvEo/default.jpg)
![Generate All Strings With n Matched Parentheses - Backtracking ("Generate Parentheses" on LeetCode)](https://i.ytimg.com/vi/sz1qaKt0KGQ/default.jpg)
![](https://i.ytimg.com/vi/tsLY_WahQU8/default.jpg)
![Search A 2D Sorted Matrix - Fundamentals of Search Space Reduction](https://i.ytimg.com/vi/FOa55B9Ikfg/default.jpg)
![Maximum Sum Rectangular Submatrix in Matrix dynamic programming/2D kadane](https://i.ytimg.com/vi/yCQN096CwWM/default.jpg)
![Why Comparison Based Sorting Algorithms Are Ω(n*lg(n))](https://i.ytimg.com/vi/WffUZk1pgXE/default.jpg)
![Total Occurrences Of K In A Sorted Array (Facebook Software Engineering Interview Question)](https://i.ytimg.com/vi/RlXtTF34nnE/default.jpg)
![Top “Hard” Interview Problems from Google, Facebook, FANG (for software engineers)](https://i.ytimg.com/vi/QGVCnjXmrNg/default.jpg)
![Maximum Size Rectangle of All 1's Dynamic Programming](https://i.ytimg.com/vi/g8bSdXCG-lA/default.jpg)
![Maximum area rectangle in a binary matrix | Leetcode #85 | Maximal rectangle](https://i.ytimg.com/vi/dAVF2NpC3j4/default.jpg)
![Implement A Max Stack - A Stack With A .max() API (Similar To "Min Stack" on LeetCode)](https://i.ytimg.com/vi/nGwn8_-6e7w/default.jpg)
![Count Total Unique Binary Search Trees - The nth Catalan Number (Dynamic Programming)](https://i.ytimg.com/vi/GgP75HAvrlY/default.jpg)
![Egg Dropping Problem: Dynamic Programming Fundamentals & Understanding Subproblem Decomposition](https://i.ytimg.com/vi/iOaRjDT0vjc/default.jpg)
![The Backtracking Blueprint: The Legendary 3 Keys To Backtracking Algorithms](https://i.ytimg.com/vi/Zq4upTEaQyM/default.jpg)
![Next Greater Element | Two Variants | Leetcode](https://i.ytimg.com/vi/Du881K7Jtk8/default.jpg)
![Kadane's Algorithm - Maximum Sum Subarray (Amazon Coding Interview Question)](https://i.ytimg.com/vi/jnoVtCKECmQ/default.jpg)
![Illustrated Guide to Transformers Neural Network: A step by step explanation](https://i.ytimg.com/vi/4Bdc55j80l8/default.jpg)