1727. Largest Submatrix With Rearrangements
Description
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.length
n == matrix[i].length
1 <= m * n <= 105
matrix[i][j]
is either0
or1
.
Solutions
Solution 1: Preprocessing + Sorting
Since the matrix is rearranged by columns according to the problem, we can first preprocess each column of the matrix.
For each element with a value of $1$, we update its value to the maximum consecutive number of $1$s above it, that is, $matrix[i][j] = matrix[i-1][j] + 1$.
Next, we can sort each row of the updated matrix. Then traverse each row, calculate the area of the largest sub-matrix full of $1$s with this row as the bottom edge. The specific calculation logic is as follows:
For a row of the matrix, we denote the value of the $k$-th largest element as $val_k$, where $k \geq 1$, then there are at least $k$ elements in this row that are not less than $val_k$, forming a sub-matrix full of $1$s with an area of $val_k \times k$. Traverse each element of this row from large to small, take the maximum value of $val_k \times k$, and update the answer.
The time complexity is $O(m \times n \times \log n)$. Here, $m$ and $n$ are the number of rows and columns of the matrix, respectively.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|