Java | Simple | Detailed Explanation | Histogram Approach | O(n^2)
Note:\nIf you haven\'t solved the Largest Rectangle in Histogram problem, I\'d highly recommend to solve that first. You can check my detailed explanation for t
**Note:**\nIf you haven\'t solved the [Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram) problem, I\'d highly recommend to solve that first. You can check my detailed explanation for the same [here](https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/1255567/Java-or-Explanation-or-Stack-approach).\n\nApproach:\n1. The idea here is to break the problem in parts. We see each set of rows as a histogram, and evaluate the height of the building considering row in consideration/iteration currently as the base, and evaluating the maximum area using above mentioned **Histogram** approach.\n2. Then we continue to next row and consider the imaginary histogram with this row as base, and again evaluate the maximum area in this histogram.\n3. Similarly, we do the above at each row, and keep updating the **maxArea** and have the max. rectangle area at the end.\n\nFor example, if the matrix is:\n1 0 1 0 0\n1 0 1 1 1\n1 1 1 1 1\n1 0 0 1 0\n\n**Round-1:**\nWe consider row-1. Histogram at this point is, `1 0 1 0 0`.\nHere, `heights[0] = [1,0,1,0,0]`.\n\n**Round-2:**\nWe consider row-1 and row-2.\nSo now, histogram is of max. height 2, and buildings are like:\n`1 0 1 0 0`\n`1 0 1 1 1`\nSo, here, `heights[1] = [2 0 2 1 1]`.\n\nSimilarly, at next levels,\n`heights[3] = [3 1 3 2 2]`\n`heights[4] = [4 0 0 3 0]`\n\n```\nclass Solution {\n    public int maximalRectangle(char[][] matrix) {\n        if (matrix.length == 0)\n            return 0;\n        int m = matrix.length, n = matrix[0].length;\n        int[] heights = new int[n];\n        int maxArea = 0;\n\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (matrix[i][j] == \'0\')\n                    heights[j] = 0;\n                if (matrix[i][j] == \'1\')\n                    heights[j] += 1;\n            }\n            maxArea = Math.max(maxArea, largestRectangleArea(heights));\n        }\n        return maxArea;\n    }\n\n    private int largestRectangleArea(int[] heights) {\n        Stack<int[]> stack = new Stack<>();\n        int maxArea = 0;\n\n        for (int i = 0; i < heights.length; i++) {\n            int[] block = new int[]{i, heights[i]};\n            while (!stack.isEmpty() && stack.peek()[1] > heights[i]) {\n                block = stack.pop();\n                maxArea = Math.max(maxArea, block[1] * (i - block[0]));\n                block[1] = heights[i];\n            }\n            stack.push(block);\n        }\n        while (!stack.isEmpty()) {\n            int[] block = stack.pop();\n            maxArea = Math.max(maxArea, block[1] * (heights.length - block[0]));\n        }\n        return maxArea;\n    }\n}\n```\n\n-------------------------------------------------------------------------------------------\nHope this helps! Please let me know if something isn\'t clear/missing. I\'ll try to improve.\n\nAlso, please upvote this if you find this useful. Happy Coding!!
['Stack', 'Java']