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.
1var maximalRectangle = function(matrix) {
2 if (!matrix.length || !matrix[0].length) return 0;
3 let maxArea = 0;
4 const cols = matrix[0].length;
5 const heights = new Array(cols + 1).fill(0);
6
7 for (let row of matrix) {
8 for (let i = 0; i < cols; i++) {
9 if (row[i] === '1') {
10 heights[i] += 1;
11 } else {
12 heights[i] = 0;
13 }
14 }
15
16 const stack = [-1];
17 for (let i = 0; i < heights.length; i++) {
18 while (heights[i] < heights[stack[stack.length - 1]]) {
19 const h = heights[stack.pop()];
20 const w = i - 1 - stack[stack.length - 1];
21 maxArea = Math.max(maxArea, h * w);
22 }
23 stack.push(i);
24 }
25 }
26 return maxArea;
27};Like the Python solution, this JavaScript approach uses histograms derived from each row. Each column height is updated based on the current row's values, and a stack is used to calculate potential maximum rectangular areas 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.