The challenge
Return the largest area of an all-ones axis-aligned rectangle in a binary matrix.
Rectangular matrix of numeric 0 and 1; an empty matrix returns 0.
Example
[[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]] → 6.
Use the walkthrough below to inspect the input and each state change.
See Maximal Rectangle in a Binary Matrix, step by step
Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.
Zero-based input · top labeled explicitlyLIFO
| Row 0 | 1 | 0 | 1 | 0 | 0 |
|---|---|---|---|---|---|
| Row 1 | 1 | 0 | 1 | 1 | 1 |
| Row 2 | 1 | 1 | 1 | 1 | 1 |
| Row 3 | 1 | 0 | 0 | 1 | 0 |
- Current input index
- —
- Main stack size
- 0
Step 01 / 39
Start with an empty stack
Read the input in order. The stack keeps only the state needed to resolve the next item.
Answer so far
Not recorded yet
- Main stack · bottom → top
- Empty
- Auxiliary stack · bottom → top
- Empty
View exact input and state
Input: [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]
Main stack: []. Auxiliary stack · bottom → top: [].
Put it into code
Accumulate column heights for each row; zero resets a height.
Indices are zero-based. C++ uses C++17 or later.
def histogram(heights):
stack, best = [], 0
for i in range(len(heights) + 1):
height = heights[i] if i < len(heights) else 0
while stack and heights[stack[-1]] > height:
j = stack.pop()
left = stack[-1] if stack else -1
best = max(best, heights[j] * (i - left - 1))
if i < len(heights): stack.append(i)
return best
def solve(matrix):
heights = [0] * (len(matrix[0]) if matrix else 0)
best = 0
for row in matrix:
for c, value in enumerate(row):
heights[c] = heights[c] + 1 if value else 0
best = max(best, histogram(heights))
return best
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
long long histogram(const vector<int>& heights) {
vector<int> stack;
long long best = 0;
int n = static_cast<int>(heights.size());
for (int i = 0; i <= n; ++i) {
int height = i < n ? heights[i] : 0;
while (!stack.empty() && heights[stack.back()] > height) {
int j = stack.back(); stack.pop_back();
int left = stack.empty() ? -1 : stack.back();
best = max(best, 1LL * heights[j] * (i - left - 1));
}
if (i < n) stack.push_back(i);
}
return best;
}
long long solve(const vector<vector<int>>& matrix) {
vector<int> heights(matrix.empty() ? 0 : matrix[0].size(), 0);
long long best = 0;
for (const auto& row : matrix) {
for (int c = 0; c < static_cast<int>(heights.size()); ++c)
heights[c] = row[c] ? heights[c] + 1 : 0;
best = max(best, histogram(heights));
}
return best;
}