Maximal Rectangle

Maximal Rectangle

What is this problem about?

The Maximal Rectangle problem gives you a 2D binary matrix filled with 0s and 1s. You need to find the largest rectangular area that contains only 1s and return its area. For example, in a grid where a block of 2x3 1s exists, the maximum area is 6.

Why is this asked in interviews?

This is a pinnacle Hard-level problem that frequently appears in FAANG onsite interviews. It tests a candidate's ability to layer algorithms. It requires taking a 2D matrix problem and reducing it row-by-row into a famous 1D problem ("Largest Rectangle in Histogram"). It demonstrates a deep understanding of state accumulation and Monotonic Stacks.

Algorithmic pattern used

This problem uses Dynamic Programming (State Accumulation) combined with the Monotonic Stack pattern.

1. Create a 1D array heights representing the height of consecutive 1s in the current row.
2. Iterate through each row in the matrix. Update heights: if matrix[row][col] == '1', heights[col]++. If it's '0', reset heights[col] = 0.
3. After updating the heights array for a row, treat it as a histogram. Use a Monotonic Stack to calculate the largest rectangle in that specific histogram.
4. Keep a running global maximum of these calculated areas across all rows.

Example explanation

Matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

• Row 0: heights = [1, 0, 1, 0, 0]. Largest rectangle area is 1.
• Row 1: heights = [2, 0, 2, 1, 1]. (Accumulated from previous row). Largest area: the last three columns [2, 1, 1] can form a rectangle of height 1 and width 3 (area 3), or height 2 width 1 (area 2). Max is 3.
• Row 2: heights = [3, 1, 3, 2, 2]. Largest rectangle: columns index 2, 3, 4 have heights [3, 2, 2]. They can form a rectangle of height 2 and width 3. Area = 6.
• Row 3: heights = [4, 0, 0, 3, 0]. The zeroes destroy the towers! Largest area here is 4. Global max area is 6.

Common mistakes candidates make

Candidates often try to solve this by searching for all possible top-left and bottom-right corners using 4 nested loops. This $O((M \times N)^2)$ approach results in an instant Time Limit Exceeded. Another common error is forgetting to completely reset the histogram column height to 0 when a '0' is encountered; a zero severs the foundation, destroying the tower above it.

Interview preparation tip

Do not attempt the Maximal Rectangle coding problem until you have thoroughly mastered the "Largest Rectangle in Histogram" problem. The logic to solve a single row's histogram using a Monotonic Stack is about 15 lines of dense code. Once you can write the Histogram logic smoothly, wrapping it in a single for loop that updates heights row-by-row makes this daunting Hard problem remarkably manageable.