Sponsored
Sponsored
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;
}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.