This is a classic extension of 84. Largest Rectangle in Histogram.
1. Problem Statement (Simple Explanation)
You’re given a binary matrix matrix of size rows x cols filled with '0's and '1's.
You must find the area of the largest rectangle containing only '1's and return that area.
The rectangle must be axis-aligned.
It can span multiple rows and columns.
2. 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"]
]
Largest all-ones rectangle has area 6:
For example, from row 1 to row 2, columns 2 to 4 (0-based), i.e.:
[
[1,1,1],
[1,1,1]
]
Output: 6
Example 2:
Input: [["0"]]
No '1's → max area = 0.
Output: 0
Example 3:
Input: [["1"]]
Single cell '1' → max area = 1.
Output: 1
3. Approach – Treat Each Row as Base of a Histogram (O(rows * cols))
This problem can be reduced to repeated applications of Largest Rectangle in Histogram (Problem 84).
Key Insight:
For each row i, we can consider that row as the base of a histogram where:
heights[j] = number of consecutive '1's above (and including) row i in column j.
Formally:
if matrix[i][j] == '1':
heights[j] = heights[j] + 1
else:
heights[j] = 0
Then, for each row i, we compute the largest rectangle area in the histogram described by heights.
The maximum over all rows is the answer.
We already have an O(n) solution for largest rectangle in histogram (using a monotonic stack).
Here n = cols and we do it for each row: overall O(rows * cols).
3.1 Largest Rectangle in Histogram (Recap)
Given heights[], we can compute largest rectangle area using a monotonic increasing stack:
Append a sentinel 0 at the end to flush stack.
For each index i:
While stack not empty and heights[i] < heights[stack.top()]:
Pop mid = stack.top.
height = heights[mid]
Right boundary = i
Left boundary = stack.top() if any, else -1
Width = right - left - 1
Area = height * width.
Push i.
3.2 Overall Algorithm
If matrix is empty, return 0.
Let cols = matrix[0].length.
Maintain an array heights of size cols, initialized to 0.
For each row i from 0 to rows - 1:
Update heights[j]:
If matrix[i][j] == '1' → heights[j]++
Else → heights[j] = 0
Compute maxRectRow = largestRectangleArea(heights).
Track global maxArea = max(maxArea, maxRectRow).
Return maxArea.
Pseudo-code:
Where largestRectangleArea(heights) is implemented as in Problem 84.
Complexity:
Let R = rows, C = cols.
Updating heights for each row: O(C) per row.
Largest rectangle per row: O(C) with stack.
Overall: O(R * C) time.
Space: O(C) for heights + O(C) for the stack = O(C).
Given rows, cols <= 200, this is efficient.
4. Java code
5. C++ code
6. C code
7. Python code
8. JavaScript code
Comments
Post a Comment