Log inSign up
hardLeetCodeNot Started

Maximal Rectangle

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 matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example 1 · Standard 4x5 Matrix:

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 has area = 6 (rows 1-2, cols 2-4 with 2 rows x 3 cols of 1s).

Example 2 · Single Zero Matrix:

Input: matrix = [["0"]]
Output: 0
Explanation: No 1s exist in the matrix.

Example 3 · Single One Matrix:

Input: matrix = [["1"]]
Output: 1
Explanation: Single 1 cell has area 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 row iteration & running prefix accumulations
  • Stack push/pop amortized time analysis

What You'll Learn

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

  • Learn the technique of reducing 2D grid problems into 1D histogram subproblems.
  • Master the Monotonic Increasing Stack algorithm for finding Previous and Next Smaller Elements.
  • Compress 2D state into a 1D rolling array.

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 SquareMaximum Rectangle in Binary Matrix

1. Brute Force — Width Accumulation with Upward Column Scans

Intuition

For each cell, precompute the width of consecutive 1s ending at that cell. For each cell (r, c), scan upwards through rows k from r down to 0, tracking minimum width and updating area minWidth * (r - k + 1).

Algorithm

  1. Step 1: Compute width[r][c] = number of consecutive 1s ending at (r, c).
  2. Step 2: For each cell (r, c), iterate k from r down to 0.
  3. Step 3: Track minWidth = min(minWidth, width[k][c]).
  4. Step 4: Update maxArea = max(maxArea, minWidth * (r - k + 1)).

Width Accumulation with Upward Column Scans Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [r0: [1,0,1], r1: [1,1,1], r2: [0,1,1]]
Current operationSTEP 1 OF 6
Matrix 3x3: r0: ['1','0','1'], r1: ['1','1','1'], r2: ['0','1','1']
Visual state
Values and pointers at this exact step
pointers
S
1
0
1
0
↑ r0 max=1
1
2
Variables at this step
r
0
maxArea
1
Check / comparison
r0 widths: [1, 0, 1]
Decision / next transition
Max area in row 0 is 1.
Why this step matters

Matrix 3x3: r0: [1,0,1], r1: [1,1,1], r2: [0,1,1]. Compute width of consecutive 1s.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int maximalRectangle(vector<vector<char>>& matrix) {
10 if (matrix.empty() || matrix[0].empty()) return 0;
11 int m = matrix.size(), n = matrix[0].size();
12 vector<vector<int>> width(m, vector<int>(n, 0));
13 int maxArea = 0;
14
15 for (int r = 0; r < m; r++) {
16 for (int c = 0; c < n; c++) {
17 if (matrix[r][c] == '1') {
18 width[r][c] = (c == 0 ? 1 : width[r][c - 1] + 1);
19
20 int minWidth = width[r][c];
21 for (int k = r; k >= 0 && matrix[k][c] == '1'; k--) {
22 minWidth = min(minWidth, width[k][c]);
23 maxArea = max(maxArea, minWidth * (r - k + 1));
24 }
25 }
26 }
27 }
28
29 return maxArea;
30 }
31};
32
33int main() {
34 Solution sol;
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 cout << "Maximal Rectangle Area (Width Scan): " << sol.maximalRectangle(matrix) << "\n";
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(M^2 * N) — Precomputes consecutive left widths in O(M * N), then for each cell scans up to M rows upward.
  • Space complexity: O(M * N) — Stores an M x N integer table of horizontal widths.

Why Brute Force Doesn't Scale:

For a 200x200 matrix, 2006 = 6.4 * 1013 operations, taking days to finish.

Monotonic stack reduction processes 200x200 in 40,000 operations (< 1ms).

2. Better — Histogram with Explicit Left/Right Boundary Arrays

Intuition

Maintain height, left, and right limit arrays across rows. Update left boundary based on current row 0s, and right boundary accordingly. The area is (right[j] - left[j]) * height[j].

Algorithm

  1. Step 1: Maintain arrays h[n], left[n], right[n] initialized to 0 and n.
  2. Step 2: For each row, update heights: if 1 h[j]++, else h[j] = 0.
  3. Step 3: Update left boundaries using current row leftmost 1 position.
  4. Step 4: Update right boundaries using current row rightmost 1 position.
  5. Step 5: Area = max(maxArea, (right[j] - left[j]) * h[j]).

Histogram with Explicit Left/Right Boundary Arrays Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [h=[0,2,2], left=[0,1,1], right=[0,2,2]]
Current operationSTEP 1 OF 6
Row 0: heights = [1, 0, 1]
Visual state
Values and pointers at this exact step
pointers
S
1
0
1
0
1
2
Variables at this step
r
0
heights
[1,0,1]
maxArea
1
Check / comparison
Row 0 max area = 1
Decision / next transition
Advance to Row 1.
Why this step matters

Row 0: heights = [1, 0, 1]. Compute left and right boundaries for each bar. Max area = 1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int maximalRectangle(vector<vector<char>>& matrix) {
10 if (matrix.empty() || matrix[0].empty()) return 0;
11 int m = matrix.size(), n = matrix[0].size();
12
13 vector<int> left(n, 0), right(n, n), height(n, 0);
14 int maxArea = 0;
15
16 for (int r = 0; r < m; r++) {
17 int curLeft = 0, curRight = n;
18
19 // Update height
20 for (int c = 0; c < n; c++) {
21 if (matrix[r][c] == '1') height[c]++;
22 else height[c] = 0;
23 }
24
25 // Update left bound
26 for (int c = 0; c < n; c++) {
27 if (matrix[r][c] == '1') left[c] = max(left[c], curLeft);
28 else { left[c] = 0; curLeft = c + 1; }
29 }
30
31 // Update right bound
32 for (int c = n - 1; c >= 0; c--) {
33 if (matrix[r][c] == '1') right[c] = min(right[c], curRight);
34 else { right[c] = n; curRight = c; }
35 }
36
37 // Compute area
38 for (int c = 0; c < n; c++) {
39 maxArea = max(maxArea, (right[c] - left[c]) * height[c]);
40 }
41 }
42
43 return maxArea;
44 }
45};
46
47int main() {
48 Solution sol;
49 vector<vector<char>> matrix = {
50 {'1','0','1','0','0'},
51 {'1','0','1','1','1'},
52 {'1','1','1','1','1'},
53 {'1','0','0','1','0'}
54 };
55 cout << "Maximal Rectangle Area (Boundary DP): " << sol.maximalRectangle(matrix) << "\n";
56 return 0;
57}

Time & Space Complexity

  • Time complexity: O(M * N) — Precomputes left and right bounds per row in linear passes.
  • Space complexity: O(N) — Maintains 3 arrays of size N (height, left boundary, right boundary).

3. Optimal — Histogram Reduction + Monotonic Stack

Intuition

Maintain a running 1D heights array. For each row: if matrix[r][c] == '1', increment heights[c]++; else reset heights[c] = 0. Then apply the optimal Monotonic Stack 'Largest Rectangle in Histogram' algorithm on heights in linear O(N) time.

Algorithm

  1. Step 1: Initialize heights vector of size N with 0.
  2. Step 2: For each row: update heights[c] = matrix[r][c] == '1' ? heights[c] + 1 : 0.
  3. Step 3: Calculate Largest Rectangle in Histogram on heights using a monotonic increasing stack.
  4. Step 4: Stack pops elements when a smaller height is found, computing area = h * (i - stack.top() - 1).
  5. Step 5: Track global maxArea = max(maxArea, largestHistogramArea).

Histogram Reduction + Monotonic Stack Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [h=[0,2,2,0], stack: indices of heights]
Current operationSTEP 1 OF 6
Row 0: heights = [1, 0, 1]
Visual state
Values and pointers at this exact step
pointers
S
1
0
1
0
1
2
Variables at this step
r
0
maxArea
1
Check / comparison
Row 0 max = 1
Decision / next transition
Advance to Row 1.
Why this step matters

Row 0: heights = [1, 0, 1]. Monotonic stack computes max rectangle = 1.

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

Time & Space Complexity

  • Time complexity: O(M * N) — Updating heights takes O(N) per row. The monotonic stack pushes and pops each index once, taking O(N) amortized time per row. Total = M * O(N) = O(M * N).
  • Space complexity: O(N) — Requires a 1D heights vector of size N and stack of size N.

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 Coordinate Sub-rectanglesO(M^3 * N^3)O(1)Enumerate all pairs of top-left (r1, c1) and bottom-right (r2, c2) coordinates and verify if all cells inside are 1.Iterating all sub-rectangles and scanning internal cells.
2.Better — Row Width Accumulation DPO(M^2 * N)O(M * N)Precompute consecutive 1s to the left for each cell. For each cell (r, c), scan upward to find minimum width for all heights.Vertical upward scans per cell.
3.Optimal — Histogram Reduction + Monotonic StackOptimalO(M * N)O(N)Maintain a 1D running heights array. For each row, update heights and solve Largest Rectangle in Histogram using a monotonic stack in O(N) amortized time.None; theoretical optimum.

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:

  • All zero matrix — Heights remain all 0, returns 0.
  • Single cell matrix [['1']] — Returns 1.
  • Matrix of all 1s — Returns M * N.

Interview Tips & Best Practices

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

  1. Explain the reduction from 2D matrix to 1D histogram problem before writing any code.
  2. Be prepared to code the monotonic stack subroutine largestRectangleArea cleanly from memory.
  3. Emphasize the O(N) amortized time per row because every index is pushed and popped at most once.

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 Maximal Rectangle?

2.Why is the brute force approach suboptimal for large inputs in Maximal Rectangle?

3.Which data structure or technique enables the optimal solution for Maximal Rectangle?

Back to DSA Sheet