Maximum size rectangle of 1s in a binary matrix

Hard

Problem

Return the area of the largest rectangle that contains only 1s in a binary matrix.

Example 1

Input:  [[0,1,1,0], [1,1,1,1], [1,1,1,1], [1,1,0,0]]
Output: 8

Rows 1–2, all four columns.

Also asked as: Maximum size rectangle

Test cases

Case 1

Input:    [[0,1,1,0],[1,1,1,1],[1,1,1,1],[1,1,0,0]]
Expected: 8

Case 2

Input:    [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]
Expected: 6

Case 3

Input:    [[1]]
Expected: 1

Case 4

Input:    [[0,0],[0,0]]
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Row-by-row histogram + largest rectangle in histogram

Time O(R·C)Space O(C)

For each row, build a histogram of consecutive 1s upward, then run the O(n) stack-based "largest rectangle in histogram" on it.

function maximalRectangle(m) {
const C = m[0].length;
const heights = Array(C).fill(0);
let best = 0;
for (const row of m) {
for (let c = 0; c < C; c++) heights[c] = row[c] ? heights[c] + 1 : 0;
best = Math.max(best, largestInHistogram(heights));
}
return best;
}
function largestInHistogram(h) {
const st = [];
let best = 0;
for (let i = 0; i <= h.length; i++) {
const cur = i === h.length ? 0 : h[i];
while (st.length && h[st[st.length - 1]] >= cur) {
const height = h[st.pop()];
const width = st.length ? i - st[st.length - 1] - 1 : i;
best = Math.max(best, height * width);
}
st.push(i);
}
return best;
}