Maximal Rectangle (Largest Rectangle of All 1s in a Binary Matrix)
Hard · Algorithms · Topics: dynamic programming, stack, histogram
The problem
Back at the warehouse robotics team — the "square staging zones" analysis wasn't flexible enough for the operations team. They actually want the single largest rectangular zone (not necessarily square) that can be marked off entirely within occupied (1) tiles, to fit the biggest possible piece of equipment. Given a binary matrix, find the area of the largest rectangle containing only 1s.
Example:
matrix = [
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
→ largest rectangle has area 6 (formed by rows 1-2, columns 2-4).
Function signature
int maximalRectangle(vector<vector<char>>& matrix);
Best rectangle: rows 1-2, cols 2-4 (2 rows x 3 cols)
[["0"]]
0
Single zero, no rectangle possible
[["1"]]
1
Single cell, area 1
[["1","1"],["1","1"]]
4
Whole 2x2 grid is all 1s
[["0","0"],["0","0"]]
0
No 1s anywhere
[["1","1","1"],["1","1","1"],["1","1","1"]]
9
Whole 3x3 grid is all 1s
How interviewers phrase it
"Given a binary matrix, find the area of the largest rectangle made entirely of 1s."
"How would you find the maximum rectangular region of all-1s in this grid?"
This is LeetCode 85 — one of the hardest "Hard"-tagged problems commonly asked, since it requires combining TWO non-trivial techniques: building a histogram per row, then solving "Largest Rectangle in Histogram" (LeetCode 84) using a monotonic stack. Interviewers often ask the histogram subproblem first as a standalone warm-up before this.
Clarifying questions to ask
Have I solved "Largest Rectangle in Histogram" before, or should I derive that subroutine from scratch? (Critical to clarify time budget — this problem is essentially two hard problems stacked together.)
Is the matrix given as char ('0'/'1') or int (0/1)? (Matches LeetCode's exact signature using char — confirm input type to avoid type-mismatch bugs.)
What are the matrix dimension constraints? (Determines whether O(m*n) overall is required — yes, almost certainly, given this is the expected optimal complexity.)
Should I return just the area, or also the actual rectangle's coordinates/boundaries? (Standard version just wants area — confirm.)
Follow-ups to expect
"Walk through how you convert this 2D problem into a series of 1D histogram problems."
"Explain the monotonic stack approach for 'Largest Rectangle in Histogram' in detail."
"Why does using a monotonic stack give you O(n) instead of O(n²) for each histogram, and how does that affect the overall complexity?"
"Can you do this with O(n) space instead of O(m*n)?"
"What's the relationship between this problem and 'Count Square Submatrices with All Ones' you solved earlier?"
"Prove why the monotonic stack approach correctly finds the maximum rectangle, not just A valid rectangle."
Practise questions like this with a real engineer
On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.