You are given a binary matrix matrix of size m x n, and you are allowed to rearrange the columns of the matrix in any order.
Return the area of the largest submatrix within matrix where every element of the submatrix is 1 after reordering the columns optimally.
Example 1:
Input: matrix = [[0,0,1],[1,1,1],[1,0,1]] Output: 4 Explanation: You can rearrange the columns as shown above. The largest submatrix of 1s, in bold, has an area of 4.
Example 2:
Input: matrix = [[1,0,1,0,1]] Output: 3 Explanation: You can rearrange the columns as shown above. The largest submatrix of 1s, in bold, has an area of 3.
Example 3:
Input: matrix = [[1,1,0],[1,0,1]] Output: 2 Explanation: Notice that you must rearrange entire columns, and there is no way to make a submatrix of 1s larger than an area of 2.
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m * n <= 105matrix[i][j] is either 0 or 1.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.
In 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.
Java
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.
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.
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.
C#
Time Complexity: O(m * n log n) due to sorting operations.
Space Complexity: O(m * n) for storing the heights.
| Approach | Complexity |
|---|---|
| Column Height Calculation and Sorting | 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. |
| Histogram Approach | Time Complexity: O(m * n log n) due to sorting operations. |
Maximal Square - Top Down Memoization - Leetcode 221 • NeetCode • 83,339 views views
Watch 9 more video solutions →Practice Largest Submatrix With Rearrangements with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor