The Question
CodingMaximal Rectangle
Given an
m x n binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Constraints:
- rows == matrix.length
- cols == matrix[i].length
- 1 <= rows, cols <= 200
- matrix[i][j] is '0' or '1'.Java
Monotonic Stack
DP
Questions & Insights
Clarifying Questions
What are the maximum dimensions of the matrix? (e.g., 1000 \times 1000 or 200 \times 200?)
What is the data type of the input? (Is it a
char[][] containing '0' and '1' or an int[][]?)How should empty or null inputs be handled?
Are there any memory constraints that would prevent storing an auxiliary array the size of a single row?
Assumptions
The dimensions N (rows) and M (cols) are up to 1000 \times 1000.
The input is a
char[][] as per standard competitive programming formats (e.g., LeetCode).If the matrix is null or has 0 rows/cols, the result is 0.
Time complexity should be O(N \cdot M) to pass efficiently.
Thinking Process
Reduction to Histogram: A 2D rectangle problem can often be broken down into multiple 1D problems. If we fix the bottom row of a potential rectangle at row i, we can treat each column as a "bar" in a histogram. The height of the bar at column j is the number of consecutive '1's stretching upwards from row i.
Dynamic Height Updates: As we iterate through rows from top to bottom, we can maintain an array
heights[] of size M. If matrix[i][j] == '1', heights[j] increases by 1; otherwise, it resets to 0.Monotonic Stack for Histogram: For each row, the problem becomes: "Find the largest rectangle in a histogram defined by
heights[]." This sub-problem is solved in O(M) using a monotonic increasing stack. The stack helps find the nearest smaller element to the left and right for every bar, defining the maximum width for a rectangle using that bar's height.Global Maximum: Track the maximum area found across all rows to get the final result.
Implementation Breakdown
Problem Set
Functional Requirements: Return the integer area of the largest sub-matrix consisting entirely of '1's.
Constraints:
Time: O(N \cdot M) where N is the number of rows and M is the number of columns.
Space: O(M) to store the histogram heights and the stack.
Approach
Algorithm: Monotonic Stack (leveraging the "Largest Rectangle in Histogram" technique).
Data Structure:
int[] for heights, Deque or Stack for indices.Complexity:
Time: O(N \cdot M) since we process each cell a constant number of times.
Space: O(M) to store the histogram for the current row.
Implementation
Wrap Up
Advanced Topics
Space Optimization: The space complexity is O(M). This is optimal as we must at least store the state of one row. If M \gg N, we could transpose the logic to iterate through columns and maintain row heights, achieving O(\min(N, M)) space.
Alternative DP approach: There is an O(N \cdot M) DP solution using three arrays:
left[], right[], and height[]. This approach calculates the boundaries for each '1' in a single pass per row. While it has the same complexity, it can sometimes be faster due to cache-friendly array accesses and no stack overhead.Parallelization: Since the computation of each row depends on the previous row's heights, we can parallelize the height calculation across columns, but the final histogram calculation per row remains sequential. However, we can calculate heights for all cells in O(1) after a O(N \cdot M) prefix sum pre-processing, allowing some row-level parallelism for the histogram sub-problem.