85. Maximal Rectangle

Intuition

Transform each row into a histogram of consecutive 1s above it. Then the largest rectangle in each histogram (problem 84) gives the largest rectangle ending at that row. Run the histogram approach for each row in O(n) with a stack.

Algorithm

1Initialise heights[n] = 0.
2For each row: if matrix[row][col]=="1", heights[col]++; else heights[col]=0.
3Run the largest-rectangle-in-histogram algorithm on heights to get the max area for this row.
4Update overall max across all rows.

Example Walkthrough

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

1.After row 0: heights=[1,0,1,0,0]. Max rectangle=1.
2.After row 1: heights=[2,0,2,1,1]. Max rectangle=3.
3.After row 2: heights=[3,1,3,2,2]. Max rectangle=6.
4.After row 3: heights=[4,0,0,3,0]. Max rectangle=4.
5.Overall max=6.

Output: 6

Common Pitfalls

•Reset heights[col]=0 when a "0" is encountered - consecutive 1s are broken.

85.cs

// Approach: Reduce to the classic Largest Rectangle in Histogram problem, applied row by row.
// Build a heights array: heights[j] = consecutive '1's directly above row i in column j (reset on '0').
// Each row produces a histogram representing the rectangles ending at that row.
// Apply the monotonic stack algorithm on each histogram to find the maximum rectangle.
// Stack stores column indices; when a shorter bar is found, pop and compute the area.
// Time: O(m x n) — one O(n) histogram pass per row. Space: O(n) for heights and stack.

public class Solution
{
    public int MaximalRectangle(char[][] matrix)
    {
        int maxRect = 0;
        int rows = matrix.Length;
        int cols = matrix[0].Length;

        int[] height = new int[cols];
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                if (matrix[i][j] == '1')
                    height[j]++;
                else
                    height[j] = 0;
            }
            int rect = largestRectangleArea(height);
            maxRect = Math.Max(maxRect, rect);
        }

        return maxRect;
    }

    static int largestRectangleArea(int[] histo)
    {
        Stack<int> st = new Stack<int>();
        int maxA = 0;
        int n = histo.Length;
        for (int i = 0; i <= n; i++)
        {
            while (st.Count != 0 && (i == n || histo[st.Peek()] >= histo[i]))
            {
                int height = histo[st.Peek()];
                st.Pop();
                int width;
                if (st.Count == 0)
                    width = i;
                else
                    width = i - st.Peek() - 1;
                maxA = Math.Max(maxA, width * height);
            }
            st.Push(i);
        }
        
        return maxA;
    }
}

Was this solution helpful?