Maximal Rectangle solution and explanation
Google
TCS
9 more videos on this problem
L13. Maximal Rectangle | Stack and Queue Playlisttake U forward · 12:12 · 134K views
Maximal rectangle | Leetcode #85 | Maximum area rectangle in a binary matrixTechdose · 11:44 · 97K views
85. Maximal Rectangle | Leetcode Daily - PythonLeetcode Daily · 7:29 · 2K views
Maximal Rectangle | LeetCode 85 | Optimal Stack + Histogram Approach | Explained Study Placement · 19:50 · 1K views
Maximal Rectangle | LeetCode 85 | Monotonic StackSanyam IIT Guwahati · 19:11 · 1K views
Daily Leetcode #2112: Jan 11, 2026 - 85. Maximal RectangleProgramming Live with Larry · 21:08 · 631 views
LeetCode 85 Maximal Rectangle | JSer - JavaScript & AlgorithmJSer · 14:04 · 422 views
LeetCode 85 - Maximal Rectangle - JavaAlpha-Code · 27:17 · 311 views
Maximal Rectangle - Leetcode 85 - PythonTim Huang · 8:12 · 222 views
C++ leetcode 85. Maximal RectangleWindows 8.1 Tails Prower Ultra · 0:11 · 152 views
The problem
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'.
Approach overview
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.
Approach 1: Approach Using Histograms and Stack
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.
def maximalRectangle(matrix):
if not matrix:
return 0
max_area = 0
cols = len(matrix[0])
heights = [0] * (cols + 1)
for row in matrix:
for i in range(cols):
if row[i] == '1':
heights[i] += 1
else:
heights[i] = 0
stack = [-1]
for i in range(cols + 1):
while heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
w = i - 1 - stack[-1]
max_area = max(max_area, h * w)
stack.append(i)
return max_areapublic int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
int maxArea = 0;
int[] heights = new int[matrix[0].length + 1];
for (char[] row : matrix) {
for (int i = 0; i < matrix[0].length; i++) {
if (row[i] == '1') {
heights[i]++;
} else {
heights[i] = 0;
}
}
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < heights.length; i++) {
while (heights[i] < heights[stack.peek()]) {
int h = heights[stack.pop()];
int w = i - 1 - stack.peek();
maxArea = Math.max(maxArea, h * w);
}
stack.push(i);
}
}
return maxArea;
}var maximalRectangle = function(matrix) {
if (!matrix.length || !matrix[0].length) return 0;
let maxArea = 0;
const cols = matrix[0].length;
const heights = new Array(cols + 1).fill(0);
for (let row of matrix) {
for (let i = 0; i < cols; i++) {
if (row[i] === '1') {
heights[i] += 1;
} else {
heights[i] = 0;
}
}
const stack = [-1];
for (let i = 0; i < heights.length; i++) {
while (heights[i] < heights[stack[stack.length - 1]]) {
const h = heights[stack.pop()];
const w = i - 1 - stack[stack.length - 1];
maxArea = Math.max(maxArea, h * w);
}
stack.push(i);
}
}
return maxArea;
};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.
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.
Approach 2: Dynamic Programming Approach
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.
#include<vector>
#include<algorithm>
using namespace std;
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int max_area = 0;
int rows = matrix.size(), cols = matrix[0].size();
vector<int> height(cols, 0);
vector<int> left(cols, 0);
vector<int> right(cols, cols);
for (int i = 0; i < rows; ++i) {
int current_left = 0, current_right = cols;
for (int j = 0; j < cols; ++j) {
if (matrix[i][j] == '1') height[j]++;
else height[j] = 0;
}
for (int j = 0; j < cols; ++j) {
if (matrix[i][j] == '1') left[j] = max(left[j], current_left);
else { left[j] = 0; current_left = j + 1; }
}
for (int j = cols - 1; j >= 0; --j) {
if (matrix[i][j] == '1') right[j] = min(right[j], current_right);
else { right[j] = cols; current_right = j; }
}
for (int j = 0; j < cols; ++j) {
max_area = max(max_area, (right[j] - left[j]) * height[j]);
}
}
return max_area;
}public int MaximalRectangle(char[][] matrix) {
if (matrix.Length == 0 || matrix[0].Length == 0) return 0;
int maxArea = 0;
int[] height = new int[matrix[0].Length];
int[] left = new int[matrix[0].Length];
int[] right = new int[matrix[0].Length];
Array.Fill(right, matrix[0].Length);
for (int i = 0; i < matrix.Length; i++) {
int currentLeft = 0, currentRight = matrix[0].Length;
for (int j = 0; j < matrix[i].Length; j++) {
if (matrix[i][j] == '1') height[j]++;
else height[j] = 0;
}
for (int j = 0; j < matrix[i].Length; j++) {
if (matrix[i][j] == '1') left[j] = Math.Max(left[j], currentLeft);
else { left[j] = 0; currentLeft = j + 1; }
}
for (int j = matrix[i].Length - 1; j >= 0; j--) {
if (matrix[i][j] == '1') right[j] = Math.Min(right[j], currentRight);
else { right[j] = matrix[i].Length; currentRight = j; }
}
for (int j = 0; j < matrix[i].Length; j++) {
maxArea = Math.Max(maxArea, height[j] * (right[j] - left[j]));
}
}
return maxArea;
}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 3: Monotonic Stack
We can treat each row as the base of a histogram and calculate the maximum area of the histogram for each row.
Specifically, we maintain an array heights with the same length as the number of columns in the matrix, where heights[j] represents the height of the column at the j-th position with the current row as the base. For each row, we iterate through each column:
- If the current element is '1', increment
heights[j]by1. - If the current element is '0', set
heights[j]to0.
Then, we use the monotonic stack algorithm to calculate the maximum rectangle area of the current histogram and update the answer.
The specific steps of the monotonic stack are as follows:
- Initialize an empty stack
stkto store the indices of the columns. - Initialize two arrays
leftandright, representing the index of the first column to the left and right of each column that is shorter than the current column. - Iterate through the heights array
heights, first calculating the index of the first column to the left of each column that is shorter than the current column, and store it inleft. - Then iterate through the heights array
heightsin reverse order, calculating the index of the first column to the right of each column that is shorter than the current column, and store it inright. - Finally, calculate the maximum rectangle area for each column and update the answer.
The time complexity is O(m times n), where m is the number of rows in matrix and n is the number of columns in matrix.
function maximalRectangle(matrix: string[][]): number {
const n = matrix[0].length;
const heights: number[] = new Array(n).fill(0);
let ans = 0;
for (const row of matrix) {
for (let j = 0; j < n; ++j) {
if (row[j] === '1') {
heights[j] += 1;
} else {
heights[j] = 0;
}
}
ans = Math.max(ans, largestRectangleArea(heights));
}
return ans;
}
function largestRectangleArea(heights: number[]): number {
let res = 0;
const n = heights.length;
const stk: number[] = [];
const left: number[] = new Array(n);
const right: number[] = new Array(n).fill(n);
for (let i = 0; i < n; ++i) {
while (stk.length && heights[stk[stk.length - 1]] >= heights[i]) {
right[stk.pop()!] = i;
}
left[i] = stk.length === 0 ? -1 : stk[stk.length - 1];
stk.push(i);
}
for (let i = 0; i < n; ++i) {
res = Math.max(res, heights[i] * (right[i] - left[i] - 1));
}
return res;
}func maximalRectangle(matrix [][]byte) int {
n := len(matrix[0])
heights := make([]int, n)
ans := 0
for _, row := range matrix {
for j, v := range row {
if v == '1' {
heights[j]++
} else {
heights[j] = 0
}
}
ans = max(ans, largestRectangleArea(heights))
}
return ans
}
func largestRectangleArea(heights []int) int {
res, n := 0, len(heights)
var stk []int
left, right := make([]int, n), make([]int, n)
for i := range right {
right[i] = n
}
for i, h := range heights {
for len(stk) > 0 && heights[stk[len(stk)-1]] >= h {
right[stk[len(stk)-1]] = i
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
left[i] = stk[len(stk)-1]
} else {
left[i] = -1
}
stk = append(stk, i)
}
for i, h := range heights {
res = max(res, h*(right[i]-left[i]-1))
}
return res
}impl Solution {
pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
let n = matrix[0].len();
let mut heights = vec![0; n];
let mut ans = 0;
for row in matrix {
for j in 0..n {
if row[j] == '1' {
heights[j] += 1;
} else {
heights[j] = 0;
}
}
ans = ans.max(Self::largest_rectangle_area(&heights));
}
ans
}
fn largest_rectangle_area(heights: &Vec<i32>) -> i32 {
let mut res = 0;
let n = heights.len();
let mut stk: Vec<usize> = Vec::new();
let mut left = vec![0; n];
let mut right = vec![n; n];
for i in 0..n {
while let Some(&top) = stk.last() {
if heights[top] >= heights[i] {
right[top] = i;
stk.pop();
} else {
break;
}
}
left[i] = if stk.is_empty() { -1 } else { stk[stk.len() - 1] as i32 };
stk.push(i);
}
for i in 0..n {
res = res.max(heights[i] * (right[i] as i32 - left[i] - 1));
}
res
}
}Complexity comparison
| 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. |
| Monotonic Stack | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Maximal Rectangle easy or hard?
Maximal Rectangle is classified as a hard problem because it requires recognizing the reduction to the Largest Rectangle in Histogram problem. The combination of matrix processing and monotonic stack logic makes it challenging for many candidates.
How to solve Maximal Rectangle in O(m*n)?
Maintain a histogram of column heights while iterating row by row. For every row, treat the heights as a histogram and compute the largest rectangle using a monotonic increasing stack. Each column index is pushed and popped once, giving O(n) work per row and O(m*n) total complexity.
What is the best approach for Maximal Rectangle?
The most widely used approach converts each matrix row into a histogram and computes the largest rectangle using a monotonic stack. Each row updates column heights and reuses the "Largest Rectangle in Histogram" algorithm. This achieves O(m*n) time and O(n) space, which is optimal for this problem.
What data structure is used in Maximal Rectangle?
The optimal solution uses a monotonic stack along with arrays that track histogram heights. Some implementations also use dynamic programming arrays for left and right boundaries. Core topics include stacks, arrays, and matrix traversal.
What is the time complexity of Maximal Rectangle?
The optimal algorithms run in O(m*n) time where m is the number of rows and n is the number of columns. Each cell contributes to histogram updates once per row, and stack operations are amortized O(n) per row. Space complexity is typically O(n).
Maximal Rectangle Python or Java solution approach?
In Python or Java, the typical solution iterates through each matrix row, updates a height array, and calls a helper function that computes the largest histogram rectangle using a stack. The logic is identical across languages and runs in O(m*n) time.
Is Maximal Rectangle asked at Google, Amazon, or Meta?
Maximal Rectangle is considered a classic hard matrix problem and has appeared in interviews at companies like Amazon, Google, and Meta. It tests the ability to reduce a 2D problem to a 1D histogram problem and apply stack-based optimization.