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:
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 shown in the above picture.
Example 2:
Input: matrix = [["0"]] Output: 0
Example 3:
Input: matrix = [["1"]] Output: 1
Constraints:
rows == matrix.lengthcols == matrix[i].length1 <= row, cols <= 200matrix[i][j] is '0' or '1'.The key idea behind solving Maximal Rectangle is to transform each row of the matrix into a histogram. As you iterate through the rows, maintain an array heights where each value represents the number of consecutive 1s ending at the current row for that column. This converts the problem into repeatedly solving the Largest Rectangle in Histogram problem.
For every row, update the histogram heights and then use a monotonic increasing stack to compute the largest rectangle in that histogram efficiently. The stack helps determine the nearest smaller bars to the left and right, allowing you to calculate the maximum area formed by each bar.
This approach combines dynamic programming (to build heights row by row) with a stack-based optimization for histogram processing. Since each cell is processed once and each histogram calculation is linear, the overall time complexity remains efficient.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force Rectangle Expansion | O(m^2 * n) | O(1) |
| Histogram + Monotonic Stack | O(m * n) | O(n) |
NeetCode
This approach is inspired by transforming the binary matrix row by row into histograms. For each row, consider it as the base and calculate the height of '1's found upwards in each column (until a '0' is encountered, resetting the height). Using these heights, treat each row as a histogram problem where you need to find the largest rectangular area. You can apply the 'Largest Rectangle in Histogram' algorithm using a stack for efficient processing.
Time Complexity: O(n * m) where n is the number of rows and m is the number of columns.
Space Complexity: O(m), used by the 'heights' array and stack.
1def maximalRectangle(matrix):
2 if not matrix:
3 return 0
4
5 max_area = 0
6 cols = len(matrix[0])
7 heights = [0] * (cols + 1)
8
9 for row in matrix:
10 for i in range(cols):
11 if row[i] == '1':
12 heights[i] += 1
13 else:
14 heights[i] = 0
15
16 stack = [-1]
17 for i in range(cols + 1):
18 while heights[i] < heights[stack[-1]]:
19 h = heights[stack.pop()]
20 w = i - 1 - stack[-1]
21 max_area = max(max_area, h * w)
22 stack.append(i)
23
24 return max_areaThe approach uses a stack-based method to calculate the largest rectangle in every row's histogram representation. Each row computes its respective histogram heights, and a monotonically increasing stack is used to calculate the maximum possible area efficiently.
This approach involves using dynamic programming (DP) to compute not only the heights but also left and right boundaries for each row's histogram. By maintaining arrays for each row, you can determine the maximum potential width of a rectangle starting from each point and thereby compute the largest rectangle area efficiently.
Time Complexity: O(n * m) because each cell is processed in constant time.
Space Complexity: O(m), due to extra arrays for heights, and boundaries.
1#include<vector>
2#include<algorithm>
3using namespace std;
4
5int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int max_area = 0;
int rows = matrix.size(), cols = matrix[0].size();
vector<int> height(cols, 0);
vector<int> left(cols, 0);
vector<int> right(cols, cols);
for (int i = 0; i < rows; ++i) {
int current_left = 0, current_right = cols;
for (int j = 0; j < cols; ++j) {
if (matrix[i][j] == '1') height[j]++;
else height[j] = 0;
}
for (int j = 0; j < cols; ++j) {
if (matrix[i][j] == '1') left[j] = max(left[j], current_left);
else { left[j] = 0; current_left = j + 1; }
}
for (int j = cols - 1; j >= 0; --j) {
if (matrix[i][j] == '1') right[j] = min(right[j], current_right);
else { right[j] = cols; current_right = j; }
}
for (int j = 0; j < cols; ++j) {
max_area = max(max_area, (right[j] - left[j]) * height[j]);
}
}
return max_area;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Maximal Rectangle is considered a classic hard interview problem and is sometimes asked in FAANG and other top tech company interviews. It tests knowledge of stacks, dynamic programming ideas, and matrix-to-histogram transformations.
The optimal approach converts each row of the matrix into a histogram of heights and then solves the Largest Rectangle in Histogram problem using a monotonic stack. This allows efficient calculation of the maximum rectangle for every row. The total time complexity becomes O(m * n).
A monotonic stack is the most important data structure for this problem. It helps efficiently compute the largest rectangle in a histogram by tracking increasing bar heights and determining width boundaries when a smaller height appears.
Converting rows into histograms simplifies the 2D rectangle problem into a well-known 1D problem. By tracking consecutive 1s as heights, each row can be treated as a histogram, allowing the efficient stack-based largest rectangle algorithm to be applied.
In this C++ solution, three vectors are maintained for each row: height, left, and right. These vectors help in calculating the maximal rectangle that can be formed by treating each row as a histogram. Dynamic programming ensures that for each iteration all possible rectangle areas are computed while respecting prior computed values.