✅ [C++] Simple Solution w/ Explanation | Optimizations from Brute-Force to DP
We are given a matrix M and required to find the area of largest rectangle having all "1" within it.\n\n---\n\n\u274C Solution - I (Brute-Force)\n\nThe most bru
We are given a matrix `M` and required to find the area of largest rectangle having all `"1"` within it.\n\n---\n\n\u274C ***Solution - I (Brute-Force)***\n\nThe most brute force way of solving this problem would be to simply consider each and every possible rectangle and consider the maximal out of the rectangles which only consists of `1` in them\n\n```cpp\nclass Solution {\npublic:\n    int maximalRectangle(vector<vector<char>>& M) {\n        if(!size(M)) return 0;\n        int ans = 0, m = size(M), n = size(M[0]);\n        for(int start_i = 0; start_i < m; start_i++) \n            for(int start_j = 0; start_j < n; start_j++) \n                for(int end_i = start_i; end_i < m; end_i++) \n                    for(int end_j = start_j; end_j < n; end_j++) {\n                        bool allOnes = true;\n                        for(int i = start_i; i <= end_i && allOnes; i++) \n                            for(int j = start_j; j <= end_j && allOnes; j++) \n                                if(M[i][j] != \'1\') allOnes = false;                           \n                        ans = max(ans, allOnes * (end_i - start_i + 1) * (end_j - start_j + 1));\n                    }\n\n        return ans;\n    }\n};\n```\n\n***Time Complexity :*** <code>O((MN)<sup>3</sup>)</code>\n***Space Complexity :*** <code>O(1)</code>\n\n---\n\n\n\u2714\uFE0F ***Solution - II (Optimized Brute-Force)***\n\nInstead of forming every rectangle, then checking validity of rectangle, we can optimize the brute-force by only considering valid rectangles. For this, we can start from every cell and consider valid rectangle starting from that cell. \n* Let the current cell be at `(i, j)`.\n* We first consider `i`th row and find maximum column length of 1s starting from `M[i][j]`.\n* Then move to `i+1`th row and find maximum column length of 1s starting from `M[i+1][j]`. Take minimum of all lengths and find the area and keep updating max area.\n* Continue similar process till you reach last row and then repeat the process for all other cells as well.\n* Finally return maximum area found from all valid rectangles.\n\nThe below image illustrates the process for first two cells of the grid -\n\n<img src="https://assets.leetcode.com/users/images/6a6c48d6-32be-4a61-8408-309b3217cb3c_1638279969.659467.png" />\n\n\n\n```cpp\nclass Solution {\npublic:\n    int maximalRectangle(vector<vector<char>>& M) {\n        if(!size(M)) return 0;\n        int ans = 0, m = size(M), n = size(M[0]);\n        for(int i = 0; i < m; i++) \n            for(int j = 0; j < n; j++) \n                for(int row = i, colLen = n, col; row < m && M[row][j] == \'1\'; row++) {\n                    for(col = j; col < n && M[row][col] == \'1\'; col++);\n                    colLen = min(colLen, col-j);\n                    ans = max(ans, (row-i+1) * colLen);\n                }\n            \n        return ans;\n    }\n};\n```\n\n***Time Complexity :*** <code>O((MN)<sup>2</sup>)</code>\n***Space Complexity :*** <code>O(1)</code>\n\n---\n\n\u2714\uFE0F ***Solution - III (Pre-compute consecutive 1s to the right / DP)***\n\nWe can improve previous solution if we pre-compute the maximum number of 1s to the right of each cell. This will allow us to save save the iteration for finding maximum column length of 1s starting from `M[i][j]` in the previous solution. After a pre-computation which requires `O(MN)` time, we can compute the maximum column length in just `O(1)` essentially eliminating a loop from above solution.\n\n```cpp\nclass Solution {\npublic:\n    int maximalRectangle(vector<vector<char>>& M) {\n        if(!size(M)) return 0;\n        int ans = 0, m = size(M), n = size(M[0]);\n        vector<vector<short>> dp(m+1, vector<short>(n+1));\n        for(int i = m-1; ~i; i--) \n            for(int j = n-1; ~j; j--) \n                dp[i][j] = M[i][j] == \'1\' ? dp[i][j+1] + 1 : 0;\n                    \n        for(int i = 0; i < m; i++) \n            for(int j = 0; j < n; j++) \n                for(int row = i, colLen = n; row < m && M[row][j] == \'1\'; row++)\n                    ans = max(ans, (row-i+1) * (colLen = min(colLen, dp[row][j]*1)));\n                    \n        return ans;\n    }\n};\n```\n\n***Time Complexity :*** <code>O(M<sup>2</sup>N)</code>\n***Space Complexity :*** <code>O(MN)</code>\n\n---\n\n\u2714\uFE0F ***Solution - IV (Pre-compute consecutive 1s to right + number of rows above & below having atleast same number of consecutive 1s / DP)***\n\nWe can eliminate one more loop in the above solution before we arrive at the optimal solution. In previous approach, we pre-computed the number of consecutive 1s to the right of each cell (referred as `dp[i][j]` henceforth) allowing us to eliminate iterate whole columns for each row. But, still we required to iterate from each row till bottom because we didnt know if other rows below had smaller `dp[i][j]` and thus we had to keep adjusting `colLen` to hold minimum `dp[i][j]` checking for each row till the bottom.\n\nTo avoid this, we can take a slightly different approach and only **check the consecutive number of rows above and below, that have the same or greater `dp[i][j]`**. This ensures that using the current cell, we can form a rectangle of width `dp[i][j]` and use current row + number of rows above & below having same or greater `dp[i][j]`. We must note that this approach ensures that we only considering maximal area rectangle having width `dp[i][j]`, for each cell under consideration, since we are also using the max possible height for that width.\n\n**Computing `up` and `down`:**\n\nNow, the only thing remaining is how to calculate number of rows above and below having atleast `dp[i][j]`. This can be calculated from `dp` using a monotonic stack. For this, we compute two matrices `up` and `down` where `up[i][j]` will denote consecutive number of rows above `i` (and including current)  having corresponding value of `dp` for each row as atleast `dp[i][j]` and similarly `down[i][j]` denotes consecutive number of rows below `j` (and including current) each having corresponding value of `dp` for each rows as atleast equal to `dp[i][j]`.\n\nFor calculating `up` matrix- \n1. We iterate from 1st row till last row. \n2. Each time, we get a row having `dp[i][j] >= dp[s.top()][j]`, we push it into stack. \n3. If we get a row having `dp[i][j] < dp[s.top()][j]`, we pop from stack until we find row index in stack having atleast `dp[i][j]`. This helps maintain the monotonous stack. \n4. At each iteration, the value of `up[i][j]` is equal to `i-s.top()` (current row - row index on top of stack having atleast `dp[i][j]` for that row), i.e, number of consecutive rows above having atleast `dp[i][j]`.\n\nWe follow a similar approach for `down` as well.\n\n\n(*PS:* This approach\'s logic seems to be similar to other solutions based on largest rectangle in histogram, but with different implementation. Since my brute-force approaches were based on this, I have kept it same. The only difference is that for each cell, I have just used width and calculated `up` & `down` having same width instead of using height and calculating `left` & `right` having same height.)\n\n```cpp\nclass Solution {\npublic:\n    int maximalRectangle(vector<vector<char>>& M) {\n        if(!size(M)) return 0;\n        int ans = 0, m = size(M), n = size(M[0]);\n        vector<vector<short>> dp(m+1, vector<short>(n+1)), up(m, vector<short>(n,1)), down(up);\n        for(int i = m-1; ~i; i--) \n            for(int j = n-1; ~j; j--) \n                dp[i][j] = M[i][j] == \'1\' ? dp[i][j+1] + 1 : 0;\n        \n        stack<int> s;\n        for(int j = 0; j < n; j++) {\n            s = stack<int>();\n            for(int i = 0; i < m; i++) {\n                while(size(s) && dp[s.top()][j] >= dp[i][j]) s.pop();\n                up[i][j] = i - (size(s) ? s.top() : -1);\n                s.push(i);\n            }\n            s = stack<int>();\n            for(int i = m-1; ~i; i--) {\n                while(size(s) && dp[s.top()][j] >= dp[i][j]) s.pop();\n                down[i][j] = (size(s) ? s.top() : m) - i;\n                s.push(i);\n            }            \n        }\n\n        for(int i = 0; i < m; i++) \n            for(int j = 0; j < n; j++) \n                ans = max(ans, dp[i][j] * (up[i][j]+down[i][j]-1));\n                    \n        return ans;\n    }\n};\n```\n\n***Time Complexity :*** <code>O(MN)</code>\n***Space Complexity :*** <code>O(MN)</code>\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, comment below \uD83D\uDC47 \n\n---\n---
[]