Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
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 is shown in the above picture.
Example 2:
Input: matrix = [["0"]] Output: 0
Example 3:
Input: matrix = [["1"]] Output: 1
Constraints:
rows == matrix.lengthcols == matrix[i].length1 <= row, cols <= 200matrix[i][j] is '0' or '1'.Problem Overview: You are given a binary matrix filled with 0s and 1s. The task is to compute the area of the largest rectangle containing only 1s. The rectangle must be formed using adjacent cells in the grid.
Approach 1: Histograms + Monotonic Stack (O(m*n) time, O(n) space)
Convert each matrix row into a histogram. Maintain an array heights where heights[j] represents the number of consecutive 1s above the current cell (including the current row). For every row, update this histogram and compute the largest rectangle in the histogram using a monotonic increasing stack. The stack keeps column indices where heights are increasing. When a shorter bar appears, pop from the stack and calculate area using the popped height as the limiting bar.
This technique reuses the classic "Largest Rectangle in Histogram" pattern. Each column index is pushed and popped at most once, so histogram processing runs in O(n) per row. Across m rows, the total runtime becomes O(m*n). The stack stores indices only, giving O(n) extra space. This method combines stack, monotonic stack, and array processing.
Approach 2: Dynamic Programming with Left/Right Boundaries (O(m*n) time, O(n) space)
Track three arrays while scanning each row: height, left, and right. height[j] stores consecutive vertical 1s like the histogram approach. left[j] records the leftmost boundary where a rectangle of height height[j] can extend, while right[j] tracks the right boundary. Update left by scanning left-to-right and update right by scanning right-to-left.
Once these arrays are updated for the current row, compute the area for every column using (right[j] - left[j]) * height[j]. This approach effectively performs dynamic programming across rows, carrying forward rectangle constraints. Each cell is processed a constant number of times, giving O(m*n) time and O(n) space. The technique relies heavily on dynamic programming and careful boundary tracking inside the matrix.
Recommended for interviews: The histogram + monotonic stack approach is the one most interviewers expect. It shows you can transform a 2D problem into repeated 1D histogram problems and apply a known stack pattern. The dynamic programming boundary method is also optimal and sometimes easier to reason about, but the histogram technique demonstrates stronger pattern recognition.
This approach is inspired by transforming the binary matrix row by row into histograms. For each row, consider it as the base and calculate the height of '1's found upwards in each column (until a '0' is encountered, resetting the height). Using these heights, treat each row as a histogram problem where you need to find the largest rectangular area. You can apply the 'Largest Rectangle in Histogram' algorithm using a stack for efficient processing.
The approach uses a stack-based method to calculate the largest rectangle in every row's histogram representation. Each row computes its respective histogram heights, and a monotonically increasing stack is used to calculate the maximum possible area efficiently.
Python
JavaScript
Java
Time Complexity: O(n * m) where n is the number of rows and m is the number of columns.
Space Complexity: O(m), used by the 'heights' array and stack.
This approach involves using dynamic programming (DP) to compute not only the heights but also left and right boundaries for each row's histogram. By maintaining arrays for each row, you can determine the maximum potential width of a rectangle starting from each point and thereby compute the largest rectangle area efficiently.
In this C++ solution, three vectors are maintained for each row: height, left, and right. These vectors help in calculating the maximal rectangle that can be formed by treating each row as a histogram. Dynamic programming ensures that for each iteration all possible rectangle areas are computed while respecting prior computed values.
Time Complexity: O(n * m) because each cell is processed in constant time.
Space Complexity: O(m), due to extra arrays for heights, and boundaries.
| Approach | Complexity |
|---|---|
| Approach Using Histograms and Stack | Time Complexity: O(n * m) where n is the number of rows and m is the number of columns. |
| Dynamic Programming Approach | Time Complexity: O(n * m) because each cell is processed in constant time. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Histograms + Monotonic Stack | O(m*n) | O(n) | Best general solution. Common interview pattern based on Largest Rectangle in Histogram. |
| Dynamic Programming with Boundaries | O(m*n) | O(n) | Good when you prefer explicit DP state tracking instead of stack operations. |
L13. Maximal Rectangle | Stack and Queue Playlist • take U forward • 118,173 views views
Watch 9 more video solutions →Practice Maximal Rectangle with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor