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.
1public int maximalRectangle(char[][] matrix) {
2 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
3 int maxArea = 0;
4 int[] heights = new int[matrix[0].length + 1];
5
6 for (char[] row : matrix) {
7 for (int i = 0; i < matrix[0].length; i++) {
8 if (row[i] == '1') {
9 heights[i]++;
10 } else {
11 heights[i] = 0;
12 }
13 }
14
15 Stack<Integer> stack = new Stack<>();
16 stack.push(-1);
17 for (int i = 0; i < heights.length; i++) {
18 while (heights[i] < heights[stack.peek()]) {
19 int h = heights[stack.pop()];
20 int w = i - 1 - stack.peek();
21 maxArea = Math.max(maxArea, h * w);
22 }
23 stack.push(i);
24 }
25 }
26
27 return maxArea;
28}This Java solution utilizes a similar method as other languages. Heights are computed and stored for each column for each row iteration, addressing maximal rectangle calculation through stack manipulation.
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.
1public int MaximalRectangle(char[][] matrix) {
2 if (matrix.Length == 0 || matrix[0].Length == 0) return 0;
3 int maxArea = 0;
4 int[] height = new int[matrix[0].Length];
5 int[] left = new int[matrix[0].Length];
int[] right = new int[matrix[0].Length];
Array.Fill(right, matrix[0].Length);
for (int i = 0; i < matrix.Length; i++) {
int currentLeft = 0, currentRight = matrix[0].Length;
for (int j = 0; j < matrix[i].Length; j++) {
if (matrix[i][j] == '1') height[j]++;
else height[j] = 0;
}
for (int j = 0; j < matrix[i].Length; j++) {
if (matrix[i][j] == '1') left[j] = Math.Max(left[j], currentLeft);
else { left[j] = 0; currentLeft = j + 1; }
}
for (int j = matrix[i].Length - 1; j >= 0; j--) {
if (matrix[i][j] == '1') right[j] = Math.Min(right[j], currentRight);
else { right[j] = matrix[i].Length; currentRight = j; }
}
for (int j = 0; j < matrix[i].Length; j++) {
maxArea = Math.Max(maxArea, height[j] * (right[j] - left[j]));
}
}
return maxArea;
}The C# solution involves arrays similar to the C++ solution. The main idea remains the same: calculate the histogram heights and adjust the left and right boundaries to maximize the rectangle area that can be formed at each point.