📢Stack and DP: Unveiling the Secrets to Count Maximal Rectangles || Full Explanation || Mr. Robot
Unlocking the Power of Algorithms: Solving the Maximal Rectangle Problem\n\nIf you\'re a coding enthusiast or a budding programmer, you\'ve probably heard about
# Unlocking the Power of Algorithms: Solving the Maximal Rectangle Problem\n\nIf you\'re a coding enthusiast or a budding programmer, you\'ve probably heard about the Maximal Rectangle Problem. This fascinating problem is a classic in the world of computer science and is often used to demonstrate the power of dynamic programming and efficient algorithm design.\n\nIn this blog post, we\'ll dive deep into the problem and explore a solution using a clever algorithm. We\'ll provide code examples in multiple programming languages to ensure that you can follow along regardless of your coding preferences. So, whether you\'re a C++ aficionado, a Java enthusiast, a Python pro, or a JavaScript wizard, you\'re in the right place!\n\n## Understanding the Maximal Rectangle Problem\n\nThe Maximal Rectangle Problem can be defined as follows: Given a binary matrix, find the largest rectangle containing only ones and return its area. This might sound a bit complex at first, but with the right algorithm, it becomes a manageable challenge.\n\n## The Algorithm: Dynamic Programming to the Rescue\n\nThe key to solving the Maximal Rectangle Problem lies in dynamic programming. Dynamic programming is a powerful technique that involves breaking down a complex problem into smaller subproblems and reusing solutions to subproblems to avoid redundant computations. \n\n### Step 1: The `largestRectangleArea` Function\n\nFirst, let\'s take a look at the `largestRectangleArea` function. This function, written in C++, Java, Python, and JavaScript, calculates the largest rectangle area in a histogram. The idea is to use a stack to efficiently find the maximum area.\n\nHere\'s a simplified overview of the algorithm:\n\n1. Create an empty stack to store indices.\n2. Iterate through the histogram from left to right.\n3. While the stack is not empty and the current histogram value is less than the value at the index stored in the stack\'s top element, pop elements from the stack and calculate the maximum area for each popped element.\n4. Keep track of the maximum area as you iterate through the histogram.\n\nThis algorithm efficiently finds the largest rectangle area in the histogram, which we\'ll use in the next step.\n\n### Step 2: The `maximalAreaOfSubMatrixOfAll1` Function\n\nIn this step, we adapt the `largestRectangleArea` function to solve the Maximal Rectangle Problem for a binary matrix. We create a vector to store the height of each column and use dynamic programming to find the maximum rectangle area for each row.\n\n### Step 3: Bringing It All Together\n\nIn the final step, we create the `maximalRectangle` function, which takes a binary matrix as input and returns the maximum rectangle area containing only ones.\n\n\n## Dry Run of `maximalRectangle` Function\n\nWe\'ll perform a dry run of the `maximalRectangle` function using the following matrix:\n\n```python\nmatrix = [\n    [\'1\', \'0\', \'1\', \'0\', \'0\'],\n    [\'1\', \'0\', \'1\', \'1\', \'1\'],\n    [\'1\', \'1\', \'1\', \'1\', \'1\'],\n    [\'1\', \'0\', \'0\', \'1\', \'0\']\n]\n```\n\n### Step 1: Initializing Variables\n\nWe start with the given matrix:\n\n```\n1 0 1 0 0\n1 0 1 1 1\n1 1 1 1 1\n1 0 0 1 0\n```\n\nWe have two helper functions, `largestRectangleArea` and `maximalAreaOfSubMatrixOfAll1`, which are used within the `maximalRectangle` function.\n\n### Step 2: `maximalAreaOfSubMatrixOfAll1`\n\nWe enter the `maximalAreaOfSubMatrixOfAll1` function, which computes the maximal area of submatrices containing only \'1\'s. \n\n**Matrix and `height` after each row iteration:**\n\n1. Process Row 1:\n   - Matrix:\n     ```\n     1 0 1 0 0\n     ```\n   - Height: `[1, 0, 1, 0, 0]`\n\n2. Process Row 2:\n   - Matrix:\n     ```\n     1 0 1 1 1\n     ```\n   - Height: `[2, 0, 2, 1, 1]`\n\n3. Process Row 3:\n   - Matrix:\n     ```\n     1 1 1 1 1\n     ```\n   - Height: `[3, 1, 3, 2, 2]`\n\n4. Process Row 4:\n   - Matrix:\n     ```\n     1 0 0 1 0\n     ```\n   - Height: `[4, 1, 1, 3, 1]`\n\n**Maximal Area of Histogram (`largestRectangleArea`):**\n\nFor each `height`, we calculate the maximal area of the histogram using the `largestRectangleArea` function.\n\n- For the height `[1, 0, 1, 0, 0]`, the maximal area is `1`.\n- For the height `[2, 0, 2, 1, 1]`, the maximal area is `4`.\n- For the height `[3, 1, 3, 2, 2]`, the maximal area is `6`.\n- For the height `[4, 1, 1, 3, 1]`, the maximal area is `4`.\n\nThe maximal area of submatrices for each row is `[1, 4, 6, 4]`.\n\n### Step 3: `maximalRectangle`\n\nFinally, we return the maximum value from the array `[1, 4, 6, 4]`, which is `6`.\n\nThe maximal area of a submatrix containing only \'1\'s in the given matrix is `6`.\n\nThis concludes the dry run of the `maximalRectangle` function with the provided matrix.\n\n###  **Code C++ Java Python JS C#**\n```cpp []\nclass Solution {\npublic:\nint largestRectangleArea(vector < int > & histo) {\n    stack < int > st;\n    int maxA = 0;\n    int n = histo.size();\n    for (int i = 0; i <= n; i++) {\n        while (!st.empty() && (i == n || histo[st.top()] >= histo[i])) {\n            int height = histo[st.top()];\n            st.pop();\n            int width;\n            if (st.empty())\n                width = i;\n            else\n                width = i - st.top() - 1;\n            maxA = max(maxA, width * height);\n        }\n        st.push(i);\n    }\n    return maxA;\n}\nint maximalAreaOfSubMatrixOfAll1(vector<vector<char>> &mat, int n, int m) {\n   \n    int maxArea = 0;\n    vector<int> height(m, 0);\n    for (int i = 0; i < n; i++) {\n        for (int j = 0; j < m; j++) {\n            if (mat[i][j] == \'1\') height[j]++;\n            else height[j] = 0;\n        }\n        int area = largestRectangleArea(height);\n        maxArea = max(maxArea, area);\n    }\n    return maxArea;\n}\n\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        return maximalAreaOfSubMatrixOfAll1(matrix,matrix.size(),matrix[0].size());\n    }\n};\n```\n\n**Java:**\n```java []\nimport java.util.Stack;\n\npublic class Solution {\n\n    public int largestRectangleArea(int[] heights) {\n        Stack<Integer> stack = new Stack<>();\n        int maxArea = 0;\n        int n = heights.length;\n        for (int i = 0; i <= n; i++) {\n            while (!stack.isEmpty() && (i == n || heights[stack.peek()] >= heights[i])) {\n                int height = heights[stack.pop()];\n                int width = stack.isEmpty() ? i : i - stack.peek() - 1;\n                maxArea = Math.max(maxArea, width * height);\n            }\n            stack.push(i);\n        }\n        return maxArea;\n    }\n\n    public int maximalAreaOfSubMatrixOfAll1(char[][] matrix, int n, int m) {\n        int maxArea = 0;\n        int[] height = new int[m];\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                if (matrix[i][j] == \'1\') {\n                    height[j]++;\n                } else {\n                    height[j] = 0;\n                }\n            }\n            int area = largestRectangleArea(height);\n            maxArea = Math.max(maxArea, area);\n        }\n        return maxArea;\n    }\n\n    public int maximalRectangle(char[][] matrix) {\n        return maximalAreaOfSubMatrixOfAll1(matrix, matrix.length, matrix[0].length);\n    }\n}\n```\n\n**Python:**\n```python []\nclass Solution:\n    def largestRectangleArea(self, heights):\n        stack = []\n        max_area = 0\n        n = len(heights)\n        \n        for i in range(n + 1):\n            while stack and (i == n or heights[stack[-1]] >= heights[i]):\n                height = heights[stack.pop()]\n                width = i if not stack else i - stack[-1] - 1\n                max_area = max(max_area, height * width)\n            \n            stack.append(i)\n        \n        return max_area\n\n    def maximalAreaOfSubMatrixOfAll1(self, mat, n, m):\n        max_area = 0\n        height = [0] * m\n\n        for i in range(n):\n            for j in range(m):\n                if mat[i][j] == \'1\':\n                    height[j] += 1\n                else:\n                    height[j] = 0\n\n            area = self.largestRectangleArea(height)\n            max_area = max(max_area, area)\n        \n        return max_area\n\n    def maximalRectangle(self, matrix):\n        if not matrix:\n            return 0\n        n, m = len(matrix), len(matrix[0])\n        return self.maximalAreaOfSubMatrixOfAll1(matrix, n, m)\n\n```\n\n**JavaScript:**\n```javascript []\nfunction largestRectangleArea(heights) {\n    const stack = [];\n    let maxArea = 0;\n    const n = heights.length;\n    for (let i = 0; i <= n; i++) {\n        while (stack.length > 0 && (i === n || heights[stack[stack.length - 1]] >= heights[i])) {\n            const height = heights[stack.pop()];\n            const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;\n            maxArea = Math.max(maxArea, width * height);\n        }\n        stack.push(i);\n    }\n    return maxArea;\n}\n\nfunction maximalAreaOfSubMatrixOfAll1(matrix, n, m) {\n    let maxArea = 0;\n    const height = new Array(m).fill(0);\n    for (let i = 0; i < n; i++) {\n        for (let j = 0; j < m; j++) {\n            if (matrix[i][j] === \'1\') {\n                height[j]++;\n            } else {\n                height[j] = 0;\n            }\n        }\n        const area = largestRectangleArea(height);\n        maxArea = Math.max(maxArea, area);\n    }\n    return maxArea;\n}\n\nfunction maximalRectangle(matrix) {\n    return maximalAreaOfSubMatrixOfAll1(matrix, matrix.length, matrix[0].\n\nlength);\n}\n``` \n**C#**\n\n``` csharp []\nusing System;\nusing System.Collections.Generic;\n\nclass Solution\n{\n    public int MaximalRectangle(char[][] matrix)\n    {\n        if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0)\n        {\n            return 0;\n        }\n\n        int numRows = matrix.Length;\n        int numCols = matrix[0].Length;\n\n        int maxArea = 0;\n        int[] height = new int[numCols];\n\n        for (int row = 0; row < numRows; row++)\n        {\n            for (int col = 0; col < numCols; col++)\n            {\n                if (matrix[row][col] == \'1\')\n                {\n                    height[col]++;\n                }\n                else\n                {\n                    height[col] = 0;\n                }\n            }\n\n            int area = LargestRectangleArea(height);\n            maxArea = Math.Max(maxArea, area);\n        }\n\n        return maxArea;\n    }\n\n    private int LargestRectangleArea(int[] heights)\n    {\n        Stack<int> stack = new Stack<int>();\n        int maxArea = 0;\n        int n = heights.Length;\n\n        for (int i = 0; i <= n; i++)\n        {\n            while (stack.Count > 0 && (i == n || heights[stack.Peek()] >= heights[i]))\n            {\n                int h = heights[stack.Pop()];\n                int w = stack.Count == 0 ? i : i - stack.Peek() - 1;\n                maxArea = Math.Max(maxArea, h * w);\n            }\n\n            stack.Push(i);\n        }\n\n        return maxArea;\n    }\n}\n```\n---\n## Analysis\n![image.png](https://assets.leetcode.com/users/images/d8aa76b7-b17e-458d-b19a-837309caaec5_1697404824.6303465.png)\n\n---\n| Language   | Runtime (ms) | Memory (MB) |\n|------------|--------------|-------------|\n| C++        | 27           | 13.6        |\n| Java       | 13           | 44          |\n| Python     | 233          | 17.5        |\n| JavaScript | 63           | 45.2        |\n| C#         | 104          | 48.5        |\n\n---\n# Consider UPVOTING\u2B06\uFE0F\n\n![image.png](https://assets.leetcode.com/users/images/853344be-bb84-422b-bdec-6ad5f07d0a7f_1696956449.7358863.png)\n\n\n# DROP YOUR SUGGESTIONS IN THE COMMENT\n\n## Keep Coding\uD83E\uDDD1\u200D\uD83D\uDCBB\n\n -- *MR.ROBOT SIGNING OFF*\n
['Array', 'Dynamic Programming', 'Stack', 'Matrix', 'Python', 'C++', 'Java', 'Python3', 'JavaScript', 'C#']