Java | Detailed Explanation | Easy Approach | O(row*col)
\nIntuition :\n1) Pick one row\n2) Do summation of each index till that row\n\t\ti) if any index value is 0 then put 0 else previous summation + 1 \n3) Pass thi
```\nIntuition :\n1) Pick one row\n2) Do summation of each index till that row\n\t\ti) if any index value is 0 then put 0 else previous summation + 1 \n3) Pass this array to get max area (84. Largest Rectangle in Historgram)\n4) Update max area\n\n84. Largest Rectangle in Histogram\nIntuition :\n1) Max area will always have atleast one full bar height on any index\n2) Find largest rectangle including each bar one by one.\n\ta) For each bar, We have to find it\'s left limit & right limit (to know the maximum width)\n\tb) Find it\'s left limit (where we find any index\'s value is smaller than current index in left side array of curr index)\n\tc) Find it\'s right limit (where we find any index\'s value is smaller than current index in right side array of curr index\n3) Take the maximum of all the max area found by each bar.\n4) calculate area\n\t\twidth * height\nwhere width = right limit - left limit + 1\nheight = curr index\'s value\n5) Update max area & return it\n```\n```\nclass Solution {\n    public int maximalRectangle(char[][] matrix) {\n        if(matrix.length == 0)  return 0;\n        int maxArea = 0;\n        int row = matrix.length;\n        int col = matrix[0].length;\n        int[] dp = new int[col];\n        for(int i=0;i<row;i++){\n            for(int j=0;j<col;j++){\n                dp[j] = matrix[i][j] == \'1\' ? dp[j]+1 : 0;\n            }\n            //treating dp[j] as histogram, solving max area problem there and updating the max area\n            maxArea = Math.max(maxArea, findMaxAreaInHistogram(dp));\n        }\n        return maxArea;\n    }\n\t//84. Largest Rectangle in Histogram code\n    public int findMaxAreaInHistogram(int[] dp){\n        int len = dp.length;\n        int maxArea = 0;\n        int[] left = new int[len];\n        int[] right = new int[len];\n        Stack<Integer> stack = new Stack<>();\n        //traversing left to right, finding left limit\n        for(int i=0;i<len;i++){\n            if(stack.isEmpty()){\n                stack.push(i);\n                left[i] = 0;\n            }else{\n                while(!stack.isEmpty() && dp[stack.peek()] >= dp[i])\n                    stack.pop();\n                left[i] = stack.isEmpty() ? 0 : stack.peek()+1;\n                stack.push(i);\n            }\n        }\n        //doing empty to stack\n        while(!stack.isEmpty())\n            stack.pop();\n        \n        //traversing right to left, find right limit\n        for(int i=len-1;i>=0;i--){\n            if(stack.isEmpty()){\n                stack.push(len-1);\n                right[i] = len - 1;\n            }else{\n                while(!stack.isEmpty() && dp[stack.peek()] >= dp[i])\n                    stack.pop();\n                right[i] = stack.isEmpty() ? len-1 : stack.peek()-1;\n                stack.push(i);\n            }\n        }\n        //traversing the array , caculating area\n        int[] area = new int[len];\n        for(int i=0;i<len;i++){\n            area[i] = (right[i] - left[i] + 1) * dp[i];\n            maxArea = Math.max(maxArea, area[i]);\n        }\n        return maxArea;\n    }\n}\n```
['Stack', 'Java']