Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

**Example:**

Input:[ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ]Output:6

## Solution

### C# Program

public class Solution { public int MaximalRectangle(char[][] matrix) { if(matrix == null || matrix.Length == 0) return 0; int row = matrix.Length; int col = matrix[0].Length; int[] temp = new int[col]; int maxArea = 0; for(int i=0;i<row;i++) { for(int j=0;j<col;j++) { if(matrix[i][j] == '1') temp[j] += 1; else temp[j] = 0; } maxArea = Math.Max(maxArea,LargestRectangleArea(temp)); } return maxArea; } public int LargestRectangleArea(int[] heights) { Stack<int> stack = new Stack<int>(); int maxArea = 0; int i = 0; for(i=0;i<heights.Length;i++) { int currentElement = heights[i]; if(stack.Count == 0) stack.Push(i); else { int topElementInStack = heights[stack.Peek()]; if(topElementInStack <= currentElement) { stack.Push(i); } else { //Pop stack until topElementInStack <= currentElement while(stack.Count > 0 && heights[stack.Peek()] > currentElement) { int poppedElement = heights[stack.Pop()]; //Find Area if(stack.Count == 0) { int area = poppedElement * i; maxArea = Math.Max(area,maxArea); } else { int area = poppedElement * (i - stack.Peek() - 1); maxArea = Math.Max(area,maxArea); } } stack.Push(i); } } } while(stack.Count > 0) { int poppedElement = heights[stack.Pop()]; //Find Area if(stack.Count == 0) { int area = poppedElement * i; maxArea = Math.Max(area,maxArea); break; } else { int area = poppedElement * (i - stack.Peek() - 1); maxArea = Math.Max(area,maxArea); } } return maxArea; } }