Sponsored
This approach involves calculating column heights for each row and optimizing with column-wise rearrangements.
The idea is to calculate how many consecutive 1s appear in each column up to the current row. Then, for each row, we sort these heights to maximize the formation of the largest possible rectangle that can be formed with a base equal to the height of each column. The largest rectangle area for each row is calculated by iterating over the sorted heights and using them as potential heights for the rectangle base, multiplying by the number of consecutive columns with at least this height.
Time Complexity: O(m * n log n), where m is the number of rows and n is the number of columns. This is because for each row we do a sort operation.
Space Complexity: O(m * n) for the heights matrix and additional space for sorting.
1import java.util.Arrays;
2
3public class Solution {
4 public int largestSubmatrix(int[][] matrix) {
5 int m = matrix.length, n = matrix[0].length;
6 int[][] heights = new int[m][n];
7
8 // Compute heights column by column
9 for (int j = 0; j < n; j++) {
10 for (int i = 0; i < m; i++) {
11 if (matrix[i][j] == 1) {
12 heights[i][j] = (i == 0) ? 1 : heights[i - 1][j] + 1;
13 }
14 }
15 }
16
17 int maxArea = 0;
18 for (int i = 0; i < m; i++) {
19 Arrays.sort(heights[i]); // Sort each row
20 for (int j = n - 1; j >= 0; j--) {
21 maxArea = Math.max(maxArea, heights[i][j] * (n - j));
22 }
23 }
24
25 return maxArea;
26 }
27}In this Java solution, we use a similar approach to the Python code. We calculate the heights array where each element represents the maximum height of continuous 1s for each column in the matrix up to that row. We then sort each row of the heights array in descending order and calculate the maximum rectangle area by iterating through the sorted heights.
This approach treats each row as a base of a histogram. It calculates heights for consecutive 1s for each column, row-by-row. The optimal area is found by considering each row as a base and calculating the maximum rectangular area for each.
Time Complexity: O(m * n log n) due to sorting operations.
Space Complexity: O(m * n) for storing the heights.
1using System;
2
3public class Solution {
4 public int LargestSubmatrix(int[][] matrix) {
5 int m = matrix.Length, n = matrix[0].Length;
int[][] heights = new int[m][];
for (int i = 0; i < m; i++) heights[i] = new int[n];
for (int j = 0; j < n; j++) {
for (int i = 0; i < m; i++) {
if (matrix[i][j] == 1) {
heights[i][j] = (i == 0 ? 1 : heights[i - 1][j] + 1);
}
}
}
int maxArea = 0;
for (int i = 0; i < m; i++) {
Array.Sort(heights[i], (a, b) => b.CompareTo(a));
for (int j = 0; j < n; j++) {
maxArea = Math.Max(maxArea, heights[i][j] * (j + 1));
}
}
return maxArea;
}
}This C# solution computes the histogram-like heights of continuous 1s for each column. Height data is stored and sorted row by row, and we calculate maximum rectangle areas similarly by using sorted heights and maximum width derivations.