Log inSign up
hardLeetCodeNot Started

Maximum Rectangle in Binary Matrix

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example 1 · Standard Binary Grid:

Input: matrix = [['1','0','1','0','0'],['1','0','1','1','1'],['1','1','1','1','1'],['1','0','0','1','0']]
Output: 6
Explanation: The maximal rectangle is 6 formed by rows 1 to 2 and cols 2 to 4 (a 2x3 block of 1s).

Example 2 · Single 0 Matrix:

Input: matrix = [['0']]
Output: 0
Explanation: No 1s in the matrix, so maximum rectangle area is 0.

Example 3 · Single 1 Matrix:

Input: matrix = [['1']]
Output: 1
Explanation: Area of the single cell [0][0] is 1.

Constraints:

  • rows == matrix.length
  • cols == matrix[i].length
  • 1 <= row, cols <= 200
  • matrix[i][j] is 0 or 1.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Largest Rectangle in Histogram (Monotonic Stack)
  • Matrix traversal and dynamic programming state reset
  • Stack-based boundary calculation (Previous / Next Smaller Element)

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 2D grid to 1D histogram reduction technique.
  • Implement the Monotonic Increasing Stack for Largest Rectangle in Histogram in O(C).
  • Handle row-by-row height resetting on 0 cells.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Largest Rectangle in HistogramMaximal SquareTrapping Rain Water

1. All Subgrid Inspection (Brute Force)

Intuition

Enumerate every possible top-left (r1, c1) and bottom-right (r2, c2) corner, verifying that all cells contain 1.

Algorithm

  1. 1. Loop r1 from 0 to R-1 and c1 from 0 to C-1.
  2. 2. Loop r2 from r1 to R-1 and c2 from c1 to C-1.
  3. 3. Check if all cells in [r1..r2][c1..c2] are 1.
  4. 4. If valid, update maxArea.
  5. 5. Return maxArea.

Brute Force All Sub-Rectangles All-Ones Check

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1]
Current operationSTEP 1 OF 6
Phase 1 — Step 1: Step 1: Fix top-left corner (0, 0) and bottom-right corner (0, 0)
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
r0
1
↑ Top-Left (0, 0)
0
1
0
r1
1
0
1
1
r2
1
1
1
1
r3
1
0
0
1
Variables at this step
r1
0
c1
0
r2
0
c2
0
All 1s
YES
Area
1
maxArea
1
Check / comparison
Fix top-left corner at (r1=0, c1=0). Evaluate 1x1 sub-rectangle.
Decision / next transition
matrix[0][0] == '1'. Area = 1 * 1 = 1. maxArea = 1.
Why this step matters

Phase 1 — Step 1: Step 1: Fix top-left corner (0, 0) and bottom-right corner (0, 0). The cell contains 1. maxArea = 1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6// Brute Force Approach: All Subgrid Inspection
7int maximalRectangle(const vector<vector<char>>& matrix) {
8 if (matrix.empty() || matrix[0].empty()) return 0;
9 int R = matrix.size(), C = matrix[0].size();
10 int maxArea = 0;
11
12 for (int r1 = 0; r1 < R; r1++) {
13 for (int c1 = 0; c1 < C; c1++) {
14 for (int r2 = r1; r2 < R; r2++) {
15 for (int c2 = c1; c2 < C; c2++) {
16 bool allOnes = true;
17 for (int r = r1; r <= r2 && allOnes; r++) {
18 for (int c = c1; c <= c2; c++) {
19 if (matrix[r][c] != '1') {
20 allOnes = false;
21 break;
22 }
23 }
24 }
25 if (allOnes) {
26 maxArea = max(maxArea, (r2 - r1 + 1) * (c2 - c1 + 1));
27 }
28 }
29 }
30 }
31 }
32 return maxArea;
33}
34
35int main() {
36 vector<vector<char>> matrix = {
37 {'1', '0', '1', '0', '0'},
38 {'1', '0', '1', '1', '1'},
39 {'1', '1', '1', '1', '1'},
40 {'1', '0', '0', '1', '0'}
41 };
42 int result = maximalRectangle(matrix);
43 cout << "Output: " << result << endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(R^3 * C^3) — There are O(R2 * C2) rectangles; validating each takes O(R * C) time.
  • Space complexity: O(1) — Only constant extra memory used.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Row-Consecutive 1s DP (Better)

Intuition

Precompute consecutive 1s ending at each cell, then scan upward across all rows above.

Algorithm

  1. 1. Build width[R][C] table: if matrix[r][c] == 1, width[r][c] = width[r][c-1] + 1; else 0.
  2. 2. For each cell (r, c) with width[r][c] > 0: - minWidth = width[r][c] - For k from r down to 0: - if width[k][c] == 0: break - minWidth = min(minWidth, width[k][c]) - maxArea = max(maxArea, minWidth * (r - k + 1)).
  3. 3. Return maxArea.

Row-Wise Consecutive Ones Width Precomputation

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1]
Current operationSTEP 1 OF 6
Phase 1 — Store row 0 widths: Step 1: Precompute running width of 1s in each row
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
r0
1
↑ Row 0 Widths
0
1
0
r1
1
0
1
1
r2
1
1
1
1
r3
1
0
0
1
Variables at this step
Row 0 Widths
[1, 0, 1, 0]
Check / comparison
Compute width of consecutive 1s in row 0: width = [1, 0, 1, 0].
Decision / next transition
Store row 0 widths.
Why this step matters

Phase 1 — Store row 0 widths: Step 1: Precompute running width of 1s in each row. Row 0: [1, 0, 1, 0].

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6// Better Approach: Row-Consecutive 1s DP
7int maximalRectangle(const vector<vector<char>>& matrix) {
8 if (matrix.empty() || matrix[0].empty()) return 0;
9 int R = matrix.size(), C = matrix[0].size();
10 vector<vector<int>> width(R, vector<int>(C, 0));
11
12 for (int r = 0; r < R; r++) {
13 for (int c = 0; c < C; c++) {
14 if (matrix[r][c] == '1') {
15 width[r][c] = (c == 0 ? 0 : width[r][c - 1]) + 1;
16 }
17 }
18 }
19
20 int maxArea = 0;
21 for (int r = 0; r < R; r++) {
22 for (int c = 0; c < C; c++) {
23 if (width[r][c] == 0) continue;
24 int minW = width[r][c];
25 for (int k = r; k >= 0 && width[k][c] > 0; k--) {
26 minW = min(minW, width[k][c]);
27 maxArea = max(maxArea, minW * (r - k + 1));
28 }
29 }
30 }
31 return maxArea;
32}
33
34int main() {
35 vector<vector<char>> matrix = {
36 {'1', '0', '1', '0', '0'},
37 {'1', '0', '1', '1', '1'},
38 {'1', '1', '1', '1', '1'},
39 {'1', '0', '0', '1', '0'}
40 };
41 int result = maximalRectangle(matrix);
42 cout << "Output: " << result << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(R^2 * C) — Precomputing widths takes O(R * C). For each of the R * C cells, we scan up to R rows above: O(R * C * R) = O(R2 * C).
  • Space complexity: O(R * C) — Width table consumes O(R * C) memory.

3. Histogram Monotonic Stack (Optimal)

Intuition

Maintain a running column-height histogram and run the O(C) Largest Rectangle in Histogram monotonic stack algorithm on every row.

Algorithm

  1. 1. Initialize heights = array of size C filled with 0, maxArea = 0.
  2. 2. For each row r in matrix: - Update heights: if matrix[r][c] == 1: heights[c]++ else heights[c] = 0 - Run Largest Rectangle in Histogram on heights: - Maintain stack of indices - For each bar, pop taller bars and compute area = height * (right_bound - left_bound - 1) - Update maxArea = max(maxArea, area).
  3. 3. Return maxArea.

Cumulative Histogram Heights per Row + Monotonic Stack

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1]
Current operationSTEP 1 OF 6
Phase 1 — maxArea = 1: Step 1 (Row 0): Treat consecutive 1s down columns as histogram bars
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
r0
1
↑ Row 0 Histogram
0
1
0
r1
1
0
1
1
r2
1
1
1
1
r3
1
0
0
1
Variables at this step
Row
0
heights
[1, 0, 1, 0]
Row Max Area
1
Global Max Area
1
Check / comparison
Row 0: heights = [1, 0, 1, 0]. Monotonic stack finds largest rectangle in histogram = 1.
Decision / next transition
maxArea = 1.
Why this step matters

Phase 1 — maxArea = 1: Step 1 (Row 0): Treat consecutive 1s down columns as histogram bars. Heights: [1, 0, 1, 0]. Largest histogram rectangle = 1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4#include <algorithm>
5using namespace std;
6
7// Helper: Largest Rectangle in Histogram using Monotonic Stack
8int largestRectangleArea(const vector<int>& heights) {
9 stack<int> st;
10 int maxArea = 0;
11 int n = heights.size();
12
13 for (int i = 0; i <= n; i++) {
14 int h = (i == n) ? 0 : heights[i];
15 while (!st.empty() && h < heights[st.top()]) {
16 int height = heights[st.top()];
17 st.pop();
18 int width = st.empty() ? i : (i - st.top() - 1);
19 maxArea = max(maxArea, height * width);
20 }
21 st.push(i);
22 }
23 return maxArea;
24}
25
26// Optimal Approach: Histogram Monotonic Stack per Row
27int maximalRectangle(const vector<vector<char>>& matrix) {
28 if (matrix.empty() || matrix[0].empty()) return 0;
29 int R = matrix.size(), C = matrix[0].size();
30 vector<int> heights(C, 0);
31 int maxArea = 0;
32
33 for (int r = 0; r < R; r++) {
34 for (int c = 0; c < C; c++) {
35 if (matrix[r][c] == '1') {
36 heights[c]++;
37 } else {
38 heights[c] = 0;
39 }
40 }
41 maxArea = max(maxArea, largestRectangleArea(heights));
42 }
43 return maxArea;
44}
45
46int main() {
47 vector<vector<char>> matrix = {
48 {'1', '0', '1', '0', '0'},
49 {'1', '0', '1', '1', '1'},
50 {'1', '1', '1', '1', '1'},
51 {'1', '0', '0', '1', '0'}
52 };
53 int result = maximalRectangle(matrix);
54 cout << "Output: " << result << endl;
55 return 0;
56}

Time & Space Complexity

  • Time complexity: O(R * C) — Updating heights takes O(C) per row. The monotonic stack pushes/pops each bar at most once, taking O(C) per row. Total time across R rows is O(R * C).
  • Space complexity: O(C) — Heights array and monotonic stack both require O(C) auxiliary space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — All SubgridsO(R^3 * C^3)O(1)Check every possible rectangle (r1, c1) to (r2, c2) and test if all cells are 1.Testing O(R2 * C2) rectangles with O(R * C) cell scans.
2.Better — Row Width DPO(R^2 * C)O(R * C)Track consecutive 1s to the left in each cell; for each cell, scan upward finding minimum width.Scanning upward through all rows above.
3.Optimal — Histogram Monotonic StackOptimalO(R * C)O(C)Update heights array per row and run Monotonic Stack Largest Rectangle in Histogram.None; industry-standard optimal solution.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Matrix with all 0s -> returns 0.
  • Matrix with single cell 1 -> returns 1.
  • Checkerboard pattern where no 2 adjacent cells are 1 -> returns 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Maximum Rectangle in Binary Matrix?

2.Why is the brute force approach suboptimal for large inputs in Maximum Rectangle in Binary Matrix?

3.Which data structure or technique enables the optimal solution for Maximum Rectangle in Binary Matrix?

Back to DSA Sheet