Java | TC: O(RC) | SC: O(min(R,C)) | Optimal Stack solution
java\n/**\n * This solution is converting the input matrix row by row (OR column by column)\n * to Largest Rectangle in a Histogram.\n *\n * For each row (OR co
```java\n/**\n * This solution is converting the input matrix row by row (OR column by column)\n * to Largest Rectangle in a Histogram.\n *\n * For each row (OR column) cumulative height is calculated. Then use stack to\n * save the increasing height index.\n *\n * Time Complexity: O(R * C). Each element is added to stack once and popped\n * from stack once.\n *\n * Space Complexity: O(min(R,C)). We will either store a row or a column\n *\n * R = Number of rows in the matrix. C = Number of columns in the matrix.\n */\nclass Solution {\n    public int maximalRectangle(char[][] matrix) {\n        if (matrix == null) {\n            throw new IllegalArgumentException("Input matrix is null");\n        }\n        if (matrix.length == 0 || matrix[0].length == 0) {\n            return 0;\n        }\n\n        int rows = matrix.length;\n        int cols = matrix[0].length;\n\n        if (cols < rows) {\n            return maximalRectangleHelper(matrix, rows, cols, true);\n        } else {\n            return maximalRectangleHelper(matrix, cols, rows, false);\n        }\n    }\n\n    private int maximalRectangleHelper(char[][] matrix, int big, int small, boolean isColsSmall) {\n        int[] heights = new int[small];\n        int largestRectangle = 0;\n        for (int i = 0; i < big; i++) {\n            Deque<Integer> stack = new ArrayDeque<>();\n            for (int j = 0; j <= small; j++) {\n                if (j < small) {\n                    if (isColsSmall) {\n                        heights[j] = matrix[i][j] == \'0\' ? 0 : heights[j] + 1;\n                    } else {\n                        heights[j] = matrix[j][i] == \'0\' ? 0 : heights[j] + 1;\n                    }\n\n                }\n                while (!stack.isEmpty() && (j == small || heights[stack.peek()] >= heights[j])) {\n                    int h = heights[stack.pop()];\n                    int left = stack.isEmpty() ? -1 : stack.peek();\n                    largestRectangle = Math.max(largestRectangle, (j - 1 - left) * h);\n                }\n                stack.push(j);\n            }\n        }\n        return largestRectangle;\n    }\n}\n```\n\n---\n\nSolutions to other similar question on LeetCode:\n- [84. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/1519257/Java-or-TC:-O(N)-or-SC:-O(N)-or-Optimal-Stack-solution)\n
['Array', 'Stack', 'Matrix', 'Java']