Maximal Rectangle
Maximal Rectangle is a hard monotonic stack problem solved with the monotonic stack pattern.
The best approach, optimal (histogram per row + monotonic stack), runs in O(rows · cols) time and O(cols) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (row run lengths, scan upward) up.
Problem
You are given a rows x cols binary matrix filled with the characters '0' and '1'. Find the largest axis-aligned rectangle that contains only '1' cells and return its area (the number of cells inside it).
Examples
Example 1
- Input
matrix = [["1","1","0","1"],["1","1","1","1"],["0","1","1","1"],["0","1","1","0"]]- Output
6- Why
- Rows 1 to 3 in columns 1 and 2 form a 3 x 2 block of ones (rows 1 to 2 in columns 1 to 3 is another one of area 6).
Example 2
- Input
matrix = [["0"]]- Output
0- Why
- There is no 1 at all.
Example 3
- Input
matrix = [["1","0","1","1","1"]]- Output
3- Why
- With a single row the answer is the longest run of ones.
Constraints
1 <= rows, cols <= 200matrix[i][j]is'0'or'1'.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (row run lengths, scan upward) | O(rows² · cols) | O(rows · cols) |
| Optimal (histogram per row + monotonic stack) | O(rows · cols) | O(cols) |
1Brute force (row run lengths, scan upward)
O(rows² · cols)For each of the rows · cols cells, the upward scan can visit every row.O(rows · cols)The run-length table w.Let w[i][j] be the number of consecutive ones in row i ending at column j. Treat each cell as the bottom-right corner and walk upward row by row: the rectangle that spans rows k..i can be at most min(w[k..i][j]) wide. Track the best width × height.
- Compute w[i][j] = matrix[i][j] == '1' ? w[i][j - 1] + 1 : 0.
- For each cell (i, j) with w[i][j] > 0: minW = infinity; for k from i up to 0: minW = min(minW, w[k][j]); stop if 0; best = max(best, minW × (i - k + 1)).
- Return best.
class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] w = new int[m][n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (matrix[i][j] == '1') w[i][j] = (j > 0 ? w[i][j - 1] : 0) + 1;
int best = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int minW = Integer.MAX_VALUE;
for (int k = i; k >= 0 && w[k][j] > 0; k--) {
minW = Math.min(minW, w[k][j]);
best = Math.max(best, minW * (i - k + 1));
}
}
}
return best;
}
}class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
m, n = len(matrix), len(matrix[0])
w = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if matrix[i][j] == "1":
w[i][j] = (w[i][j - 1] if j > 0 else 0) + 1
best = 0
for i in range(m):
for j in range(n):
min_w = float("inf")
k = i
while k >= 0 and w[k][j] > 0:
min_w = min(min_w, w[k][j])
best = max(best, min_w * (i - k + 1))
k -= 1
return bestclass Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> w(m, vector<int>(n, 0));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (matrix[i][j] == '1') w[i][j] = (j > 0 ? w[i][j - 1] : 0) + 1;
int best = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int minW = INT_MAX;
for (int k = i; k >= 0 && w[k][j] > 0; k--) {
minW = min(minW, w[k][j]);
best = max(best, minW * (i - k + 1));
}
}
}
return best;
}
};function maximalRectangle(matrix) {
const m = matrix.length, n = matrix[0].length;
const w = Array.from({ length: m }, () => new Array(n).fill(0));
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (matrix[i][j] === "1") w[i][j] = (j > 0 ? w[i][j - 1] : 0) + 1;
let best = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let minW = Infinity;
for (let k = i; k >= 0 && w[k][j] > 0; k--) {
minW = Math.min(minW, w[k][j]);
best = Math.max(best, minW * (i - k + 1));
}
}
}
return best;
}2Optimal (histogram per row + monotonic stack)
O(rows · cols)Each row updates the histogram in O(cols), and every column index is pushed and popped once per row.O(cols)The histogram and the stack each hold up to cols entries.Keep h[j] = number of consecutive ones ending at the current row in column j. Each row turns the matrix into a histogram, and the largest rectangle whose bottom edge lies on this row is the largest rectangle in that histogram. Solve it with an increasing stack of column indices: when a lower bar arrives, pop taller bars and measure the rectangle each one can span.
- For each row: h[j] = matrix[i][j] == '1' ? h[j] + 1 : 0.
- Scan j = 0..n with a sentinel height 0 at j = n. While the stack top is taller than the current height, pop it as height H; width = j if the stack is now empty, else j - stack.top - 1; update best with H × width.
- Push j and continue. Return best after the last row.
class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[] h = new int[n];
int best = 0;
int[] stack = new int[n + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) h[j] = matrix[i][j] == '1' ? h[j] + 1 : 0;
int top = -1;
for (int j = 0; j <= n; j++) {
int cur = j == n ? 0 : h[j];
while (top >= 0 && h[stack[top]] > cur) {
int height = h[stack[top--]];
int width = top < 0 ? j : j - stack[top] - 1;
best = Math.max(best, height * width);
}
stack[++top] = j;
}
}
return best;
}
}class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
m, n = len(matrix), len(matrix[0])
h = [0] * n
best = 0
for i in range(m):
for j in range(n):
h[j] = h[j] + 1 if matrix[i][j] == "1" else 0
stack = []
for j in range(n + 1):
cur = 0 if j == n else h[j]
while stack and h[stack[-1]] > cur:
height = h[stack.pop()]
width = j if not stack else j - stack[-1] - 1
best = max(best, height * width)
stack.append(j)
return bestclass Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<int> h(n, 0);
int best = 0;
vector<int> stack;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) h[j] = matrix[i][j] == '1' ? h[j] + 1 : 0;
stack.clear();
for (int j = 0; j <= n; j++) {
int cur = j == n ? 0 : h[j];
while (!stack.empty() && h[stack.back()] > cur) {
int height = h[stack.back()];
stack.pop_back();
int width = stack.empty() ? j : j - stack.back() - 1;
best = max(best, height * width);
}
stack.push_back(j);
}
}
return best;
}
};function maximalRectangle(matrix) {
const m = matrix.length, n = matrix[0].length;
const h = new Array(n).fill(0);
let best = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) h[j] = matrix[i][j] === "1" ? h[j] + 1 : 0;
const stack = [];
for (let j = 0; j <= n; j++) {
const cur = j === n ? 0 : h[j];
while (stack.length > 0 && h[stack[stack.length - 1]] > cur) {
const height = h[stack.pop()];
const width = stack.length === 0 ? j : j - stack[stack.length - 1] - 1;
best = Math.max(best, height * width);
}
stack.push(j);
}
}
return best;
}Edge cases to test
- All zeros (answer 0)
- All ones (answer rows × cols)
- A single row or a single column
- A tall thin rectangle beating a short wide one, and the other way round
Hints
Hint 1
Fix the bottom row of the rectangle. For each column, how many consecutive ones end at that row?
Hint 2
Those counts form a histogram. The best rectangle with this bottom row is the largest rectangle in that histogram.
Hint 3
Update the histogram row by row in O(cols) and solve each one with a monotonic stack.
FAQ
What is the best time complexity for Maximal Rectangle?
Optimal (histogram per row + monotonic stack) runs in O(rows · cols) time and O(cols) extra space. Each row updates the histogram in O(cols), and every column index is pushed and popped once per row.
Which pattern does Maximal Rectangle use?
It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Next Greater Element I, Daily Temperatures, Next Greater Element II.
Is there a brute force solution for Maximal Rectangle?
Yes. Brute force (row run lengths, scan upward) takes O(rows² · cols) time and O(rows · cols) space. Let w[i][j] be the number of consecutive ones in row i ending at column j.
Which edge cases should I test for Maximal Rectangle?
All zeros (answer 0); All ones (answer rows × cols); A single row or a single column; A tall thin rectangle beating a short wide one, and the other way round.