Maximum size rectangle of 1s in a binary matrix
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
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;}