# O(n ^ 2) solution based on histogram solution in C# for reference

• This took me a while to figure out when I tried this for the first time. I had to understand and code up https://leetcode.com/problems/largest-rectangle-in-histogram/ (thanks to other comments in the discussion forum!) before I attempted this one again.

The idea is each time you iterate through a row in input matrix, keep track of the heights in a separate array (which is your histogram input). After you go through a row, calculate the maximum area for that histogram and compare it with current maximum and update it if necessary.

``````For example:
1 1 0 1
0 0 1 0

After iterating though row 1, your histogram = [1 1 0 1], current Area = 2 and so maxArea = 2
After iterating though row 2, your histogram = [0 0 1 0], current Area = 1 and so maxArea = 2

// O(n)
private int getMaxRectangleArea(int[] heights) {
int maxArea = 0;

Stack<int> rectHeights = new Stack<int>();

int current = 0;
while(current < heights.Length) {
if (rectHeights.Count == 0 || heights[rectHeights.Peek()] <= heights[current]) {
rectHeights.Push(current++);
} else {
int currHeightIndex = rectHeights.Pop();
int areaWithTop = heights[currHeightIndex] *
(rectHeights.Count == 0 ? current : current - 1 - rectHeights.Peek());
maxArea = Math.Max(maxArea, areaWithTop);
}
}

while (rectHeights.Count > 0) {
int currHeightIndex = rectHeights.Pop();
int areaWithTop = heights[currHeightIndex] * (rectHeights.Count == 0 ? current : current - 1 - rectHeights.Peek());
maxArea = Math.Max(maxArea, areaWithTop);
}

return maxArea;
}

// O(n ^ 2)
public int MaximalRectangle(char[,] matrix) {
int[] heights = new int[matrix.GetLength(1)];
int maxArea = 0;

for(int row = 0; row < matrix.GetLength(0); row++) {
for(int column = 0; column < matrix.GetLength(1); column++) {
if (matrix[row, column] == '1') {
heights[column]++;
} else if (matrix[row, column] == '0') {
heights[column] = 0;
}
}

maxArea = Math.Max(maxArea, getMaxRectangleArea(heights));
}

return maxArea;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.