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;
}
}
```