Easy Approach✅| CPP| Java| C| Python
Intuition\nTo find the largest rectangle of 1\'s in a binary matrix, we can learn the concept used in the "largest rectangle in histogram" problem. Essentially,
# Intuition\nTo find the largest rectangle of 1\'s in a binary matrix, we can learn the concept used in the "largest rectangle in histogram" problem. Essentially, we can treat each row of the matrix as the base of a histogram where each column contributes to the height of the histogram bars.\n\n# Prerequisite\n84. Largest Rectangle in Histogram\nhttps://leetcode.com/problems/largest-rectangle-in-histogram/solutions/5287725/simplest-and-easiest-solution-on-c/\n\n# Complexity\n- Time complexity: O(rows * cols)\n\n- Space complexity: O(cols)\n\n# CPP Code\n```\nclass Solution {\npublic:\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        // Return 0 if the matrix is empty\n        if (matrix.empty()) return 0;\n\n        int numRows = matrix.size();\n        int numCols = matrix[0].size();\n        vector<int> heights(numCols, 0);\n        int maxArea = 0;\n\n        for (int i = 0; i < numRows; i++) {\n            // Update the heights array\n            for (int j = 0; j < numCols; j++) {\n                if (matrix[i][j] == \'0\') {\n                    heights[j] = 0;\n                } else {\n                    heights[j] += 1;\n                }\n            }\n\n            // Vectors to store the next and previous smaller elements\' indices\n            vector<int> nextSmaller(numCols, numCols);\n            vector<int> prevSmaller(numCols, -1);\n            stack<int> s;\n\n            // Find the next smaller element for each position\n            for (int j = numCols - 1; j >= 0; j--) {\n                while (!s.empty() && heights[s.top()] >= heights[j]) s.pop();\n                if (!s.empty()) nextSmaller[j] = s.top();\n                s.push(j);\n            }\n\n            // Clear the stack for the next computation\n            while (!s.empty()) s.pop();\n\n            // Find the previous smaller element for each position\n            for (int j = 0; j < numCols; j++) {\n                while (!s.empty() && heights[s.top()] >= heights[j]) s.pop();\n                if (!s.empty()) prevSmaller[j] = s.top();\n                s.push(j);\n            }\n\n            // Calculate the area for each position and update maxArea\n            for (int j = 0; j < numCols; j++) {\n                int width = nextSmaller[j] - prevSmaller[j] - 1;\n                int area = heights[j] * width;\n                maxArea = max(maxArea, area);\n            }\n        }\n        return maxArea;\n    }\n};\n```\n# Java Code\n```\nclass Solution {\n    public int maximalRectangle(char[][] matrix) {\n        // Return 0 if the matrix is empty\n        if (matrix.length == 0) return 0;\n        \n        int numRows = matrix.length;\n        int numCols = matrix[0].length;\n        int[] heights = new int[numCols]; // Array to store the heights of histograms\n        int maxArea = 0;\n\n        for (int i = 0; i < numRows; i++) {\n            // Update the heights array for the current row\n            for (int j = 0; j < numCols; j++) {\n                if (matrix[i][j] == \'0\') {\n                    heights[j] = 0;\n                } else {\n                    heights[j] += 1;\n                }\n            }\n\n            Stack<Integer> stack = new Stack<>();\n            int[] nextSmaller = new int[numCols];\n            int[] prevSmaller = new int[numCols];\n            \n            for (int j = 0; j < numCols; j++) prevSmaller[j] = -1;\n            for (int j = 0; j < numCols; j++) nextSmaller[j] = numCols;\n\n            // Find the next smaller element for each position\n            for (int j = numCols - 1; j >= 0; j--) {\n                while (!stack.isEmpty() && heights[stack.peek()] >= heights[j]) stack.pop();\n                if (!stack.isEmpty()) nextSmaller[j] = stack.peek();\n                stack.push(j);\n            }\n\n            stack.clear(); // Clear the stack for the next computation\n\n            // Find the previous smaller element for each position\n            for (int j = 0; j < numCols; j++) {\n                while (!stack.isEmpty() && heights[stack.peek()] >= heights[j]) stack.pop();\n                if (!stack.isEmpty()) prevSmaller[j] = stack.peek();\n                stack.push(j);\n            }\n\n            // Calculate the area for each position and update maxArea\n            for (int j = 0; j < numCols; j++) {\n                int width = nextSmaller[j] - prevSmaller[j] - 1;\n                int area = heights[j] * width;\n                maxArea = Math.max(maxArea, area);\n            }\n        }\n        return maxArea;\n    }\n}\n```\n\n# C Code\n```\nint maximalRectangle(char** matrix, int matrixSize, int* matrixColSize) {\n    // Return 0 if the matrix is empty\n    if (matrixSize == 0) return 0;\n\n    int numCols = matrixColSize[0];\n    int* heights = (int*)calloc(numCols, sizeof(int)); // Array to store the heights of histograms\n    int maxArea = 0;\n\n    for (int i = 0; i < matrixSize; i++) {\n        // Update the heights array for the current row\n        for (int j = 0; j < numCols; j++) {\n            if (matrix[i][j] == \'0\') {\n                heights[j] = 0;\n            } else {\n                heights[j] += 1;\n            }\n        }\n\n        int* nextSmaller = (int*)malloc(numCols * sizeof(int));\n        int* prevSmaller = (int*)malloc(numCols * sizeof(int));\n        for (int j = 0; j < numCols; j++) prevSmaller[j] = -1;\n        for (int j = 0; j < numCols; j++) nextSmaller[j] = numCols;\n\n        int* stack = (int*)malloc(numCols * sizeof(int));\n        int top = -1;\n\n        // Find the next smaller element for each position\n        for (int j = numCols - 1; j >= 0; j--) {\n            while (top != -1 && heights[stack[top]] >= heights[j]) top--;\n            if (top != -1) nextSmaller[j] = stack[top];\n            stack[++top] = j;\n        }\n\n        top = -1;\n\n        // Find the previous smaller element for each position\n        for (int j = 0; j < numCols; j++) {\n            while (top != -1 && heights[stack[top]] >= heights[j]) top--;\n            if (top != -1) prevSmaller[j] = stack[top];\n            stack[++top] = j;\n        }\n\n        // Calculate the area for each position and update maxArea\n        for (int j = 0; j < numCols; j++) {\n            int width = nextSmaller[j] - prevSmaller[j] - 1;\n            int area = heights[j] * width;\n            if (area > maxArea) maxArea = area;\n        }\n\n        free(nextSmaller);\n        free(prevSmaller);\n        free(stack);\n    }\n\n    free(heights);\n    return maxArea;\n}\n```\n\n\n# Python Code\n```\nclass Solution(object):\n    def maximalRectangle(self, matrix):\n        """\n        :type matrix: List[List[str]]\n        :rtype: int\n        """\n        # Return 0 if the matrix is empty\n        if not matrix:\n            return 0\n        \n        numRows = len(matrix)\n        numCols = len(matrix[0])\n        heights = [0] * numCols  # Array to store the heights of histograms\n        maxArea = 0\n\n        for i in range(numRows):\n            # Update the heights array for the current row\n            for j in range(numCols):\n                if matrix[i][j] == \'0\':\n                    heights[j] = 0\n                else:\n                    heights[j] += 1\n\n            nextSmaller = [numCols] * numCols\n            prevSmaller = [-1] * numCols\n            stack = []\n\n            # Find the next smaller element for each position\n            for j in range(numCols - 1, -1, -1):\n                while stack and heights[stack[-1]] >= heights[j]:\n                    stack.pop()\n                if stack:\n                    nextSmaller[j] = stack[-1]\n                stack.append(j)\n\n            # Clear the stack for the next computation\n            stack = []\n\n            # Find the previous smaller element for each position\n            for j in range(numCols):\n                while stack and heights[stack[-1]] >= heights[j]:\n                    stack.pop()\n                if stack:\n                    prevSmaller[j] = stack[-1]\n                stack.append(j)\n\n            # Calculate the area for each position and update maxArea\n            for j in range(numCols):\n                width = nextSmaller[j] - prevSmaller[j] - 1\n                area = heights[j] * width\n                maxArea = max(maxArea, area)\n\n        return maxArea\n\n```
['Dynamic Programming', 'Stack', 'C', 'Monotonic Stack', 'Python', 'C++', 'Java']