85. Maximal Rectangle - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
You are given an $(m \times n)$ binary matrix filled with '0's and '1's. Your task is to find the largest rectangle (by area) containing only '1's and return its area.

Examples:

Example 1:

Input:
```
matrix = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
```
Output:
```
6
```
Explanation:
The maximal rectangle of 1's has an area of 6. One optimal rectangle is formed in rows 2–3 and columns 2–4 (using 0-indexing).
Example 2:

Input:
```
matrix = []
```
Output:
```
0
```
Explanation:
An empty matrix contains no rectangles.

Constraints:

$( m, n \ge 0 )$ (the matrix can be empty)
Each element of the matrix is either '0' or '1'.

Hints Before Diving into the Solution

Hint 1:
Think about converting each row of the matrix into a histogram where each column height represents the number of consecutive ones ending at that row. This way, the problem reduces to finding the largest rectangle area in a histogram.
Hint 2:
Recall the "Largest Rectangle in Histogram" problem. You can solve that efficiently using a monotonic stack in (O(n)) time. Use that approach row by row on the histogram built from the matrix.
Hint 3:
Update the histogram for each row: if a cell contains a '1', increment the height; if it’s a '0', reset the height to zero.

Approaches

Approach 1: Brute Force (Not Recommended)

Idea:
Consider every possible rectangle in the matrix and check if it contains only 1’s.
Drawback:
The time complexity is $(O(m^2 \times n^2))$ in the worst case, which is too slow for larger matrices.

Approach 2: Histogram-Based Dynamic Programming (Optimal)

Steps:

Build the Histogram:
Create an array height of size (n) (number of columns) initialized to 0. For each row in the matrix:
- If matrix[i][j] == '1', then update height[j] += 1.
- Otherwise, reset height[j] to 0.
Compute Largest Rectangle in Histogram:
For each updated histogram (i.e. for each row), apply the largest rectangle in histogram algorithm using a monotonic stack:
- Use a stack to keep track of indices with increasing height.
- When you encounter a height lower than the height at the top of the stack, calculate the area with the height of the popped index as the smallest height.
- Keep track of the maximum area found.
Result:
The answer is the maximum area encountered over all rows.

Code Implementation

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
- Building/updating the histogram takes $(O(m \times n))$ .
- For each row, computing the largest rectangle in a histogram takes (O(n)) using the stack approach.
- Total time complexity: $(O(m \times n))$ .
Space Complexity:
- The additional space is used for the heights array (size (n)) and the stack (worst-case (O(n))).
- Total space complexity: (O(n)).

Step-by-Step Walkthrough & Visual Example

Consider the sample matrix:

[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]

Row 0:

Convert row 0 into histogram heights:
heights = [1, 0, 1, 0, 0]
Largest rectangle in histogram: The maximum area is 1.

Row 1:

Update heights:
For column 0: '1' → 1 + 1 = 2.
For column 1: '0' → reset to 0.
For column 2: '1' → 1 + 1 = 2.
For column 3: '1' → 0 + 1 = 1.
For column 4: '1' → 0 + 1 = 1.
heights = [2, 0, 2, 1, 1]
Largest rectangle: Maximum area computed might be 3 (e.g., using heights [1,1]).

Row 2:

Update heights:
For column 0: '1' → 2 + 1 = 3.
For column 1: '1' → 0 + 1 = 1.
For column 2: '1' → 2 + 1 = 3.
For column 3: '1' → 1 + 1 = 2.
For column 4: '1' → 1 + 1 = 2.
heights = [3, 1, 3, 2, 2]
Largest rectangle here is 6 (for example, a rectangle covering columns 2, 3, 4 with height 2).

Row 3:

Update heights:
For column 0: '1' → 3 + 1 = 4.
For column 1: '0' → reset to 0.
For column 2: '0' → reset to 0.
For column 3: '1' → 2 + 1 = 3.
For column 4: '0' → reset to 0.
heights = [4, 0, 0, 3, 0]
Largest rectangle area might be 4 (using the column with height 4).

The maximum over all rows is 6.

Common Mistakes

Not Resetting Heights:
Failing to reset the height to 0 when a cell contains '0' will lead to incorrect histogram values.
Stack Mismanagement:
Incorrectly handling the monotonic stack (especially when calculating the width) can lead to wrong area calculations.
Boundary Conditions:
Not appending a 0 at the end of the histogram (or not handling the remaining stack elements) may cause missed rectangle calculations.

Edge Cases & Alternative Variations

Edge Case 1:
An empty matrix should return 0.
Edge Case 2:
A matrix with all '0's should return 0.
Edge Case 3:
A matrix with one row or one column.
Alternative Variation:
A similar problem is "Maximal Square" where you find the largest square (instead of rectangle) of 1’s.

Largest Rectangle in Histogram:
Directly related to this problem; practice the stack-based solution.
Maximal Square:
Another 2D DP problem that focuses on squares.
Submatrix Sum Problems:
Counting or finding submatrices that meet certain criteria.