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.
1def largestSubmatrix(matrix):
2 if not matrix: return 0
3 m, n = len(matrix), len(matrix[0])
4 heights = [[0] * n for _ in range(m)]
5
6 for i in range(n):
7 if matrix[0][i]:
8 heights[0][i] = 1
9
10 for i in range(1, m):
11 for j in range(n):
12 if matrix[i][j]:
13 heights[i][j] = heights[i - 1][j] + 1
14
15 max_area = 0
16 for i in range(m):
17 sorted_heights = sorted(heights[i], reverse=True)
18 for j in range(n):
19 max_area = max(max_area, sorted_heights[j] * (j + 1))
20 return max_areaIn the Python solution, we first calculate the heights of consecutive 1s for each cell in the matrix. We create a heights matrix that accumulates the heights of each column. Then, for each row, we sort these heights in descending order. We then iterate over the sorted heights to compute the maximum area possible by treating each height as forming a rectangle with a base of the number of columns that can extend this height.
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.
1function largestSubmatrix(matrix) {
2 if (
In the JavaScript solution, we calculate the heights of consecutive 1s for each column in a similar manner to the Python approach. We store these heights in a 2D array and sort each row in descending order to maximize rectangle height for calculations.