Maximal Rectangle — Solution in Python, Java & C++
Maximal Rectangle solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximal Rectangle is a hard coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google, Microsoft and Indeed interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Matrix, Stack, Monotonic Stack
- Asked at: Amazon, Google, Microsoft, Indeed, Directi, Arcesium
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A binary matrix is given as rows of the characters 0 and 1. Find the largest rectangle made entirely of 1s and return its area.
Example 1
Input: matrix = ["10100","10111","11111","10010"]
Output: 6
Explanation: The 2 × 3 block of 1s in the middle two rows.
Example 2
Input: matrix = ["0"]
Output: 0
Example 3
Input: matrix = ["1"]
Output: 1
Constraints
rows == matrix.lengthcols == matrix[i].length1 <= rows, cols <= 200matrix[i][j] is '0' or '1'
Hints for Maximal Rectangle
Hint 1
Treat each row as the ground of a histogram whose bars are the runs of 1s ending at that row.
Hint 2
Then the answer is the best "largest rectangle in a histogram" over all rows.
Hint 3
Solve each histogram in linear time with a stack of increasing bar heights.
How to solve Maximal Rectangle
Reduce the 2D problem to rows one-dimensional ones. For each row, heights[j] is the number of consecutive 1s ending at that row in column j; the largest all-1s rectangle whose bottom edge is that row is the largest rectangle in that histogram.
Approach
- Sweep rows, updating
heights[j]toheights[j] + 1on a1and to0on a0. - For each histogram, keep a stack of indices with increasing heights.
- When the incoming bar is not taller, pop: the popped bar's rectangle runs from just after the new stack top to just before the current index.
- A sentinel bar of height 0 past the end flushes the stack.
Why it works
Every all-1s rectangle has a bottom row, and within that row its height in each column is at most the run ending there — so it is counted by that row's histogram, and no rectangle is missed. The stack works because a bar is popped exactly when its right boundary is found, and its left boundary is the element below it, giving each bar's maximal span in O(1) amortised time.
Complexity
- Time —
O(rows · cols) - Space —
O(cols)
Pitfalls
- Resetting
heights[j]to0on a0is what keeps the bars contiguous. - Without the trailing sentinel the bars still on the stack are never measured.
- Popping on
>=rather than>is safe here: equal bars give the same maximal area when the last of them is popped.
Reference solution
Python
from typing import List
def maximalRectangle(matrix: List[str]) -> int:
m, n = len(matrix), len(matrix[0])
heights = [0] * (n + 1)
best = 0
for i in range(m):
for j in range(n):
heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0
stack = []
for j in range(n + 1):
while stack and heights[stack[-1]] >= heights[j]:
h = heights[stack.pop()]
left = stack[-1] if stack else -1
best = max(best, h * (j - left - 1))
stack.append(j)
return bestJava
public static int maximalRectangle(String[] matrix) {
int m = matrix.length, n = matrix[0].length();
int[] heights = new int[n + 1];
int[] stack = new int[n + 2];
int best = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
heights[j] = matrix[i].charAt(j) == '1' ? heights[j] + 1 : 0;
}
int top = 0;
for (int j = 0; j <= n; j++) {
while (top > 0 && heights[stack[top - 1]] >= heights[j]) {
int h = heights[stack[--top]];
int left = top > 0 ? stack[top - 1] : -1;
best = Math.max(best, h * (j - left - 1));
}
stack[top++] = j;
}
}
return best;
}C++
int maximalRectangle(vector<string>& matrix) {
int m = (int) matrix.size(), n = (int) matrix[0].size();
vector<int> heights(n + 1, 0);
int best = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
}
vector<int> stack;
for (int j = 0; j <= n; j++) {
while (!stack.empty() && heights[stack.back()] >= heights[j]) {
int h = heights[stack.back()];
stack.pop_back();
int left = stack.empty() ? -1 : stack.back();
best = max(best, h * (j - left - 1));
}
stack.push_back(j);
}
}
return best;
}JavaScript
var maximalRectangle = function(matrix) {
var m = matrix.length, n = matrix[0].length, i, j;
var heights = [];
for (j = 0; j <= n; j++) heights.push(0);
var best = 0;
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) heights[j] = matrix[i].charAt(j) === "1" ? heights[j] + 1 : 0;
var stack = [];
for (j = 0; j <= n; j++) {
while (stack.length > 0 && heights[stack[stack.length - 1]] >= heights[j]) {
var h = heights[stack.pop()];
var left = stack.length > 0 ? stack[stack.length - 1] : -1;
var area = h * (j - left - 1);
if (area > best) best = area;
}
stack.push(j);
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming