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.
Example 4:
Input: matrix = [[0,0],[0,0]] Output: 0 Explanation: As there are no 1s, no submatrix of 1s can be formed and the area is 0.
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m * n <= 105
matrix[i][j]
is 0
or 1
.struct Solution;
impl Solution {
fn largest_submatrix(matrix: Vec<Vec<i32>>) -> i32 {
let n = matrix.len();
let m = matrix[0].len();
let mut rows = vec![vec![0; m]; n];
for i in 0..n {
for j in 0..m {
if matrix[i][j] == 1 {
rows[i][j] = if i > 0 { rows[i - 1][j] } else { 0 } + 1;
}
}
}
let mut res = 0;
for i in 0..n {
res = res.max(Self::rearrange(&mut rows[i]));
}
res
}
fn rearrange(row: &mut Vec<i32>) -> i32 {
row.sort_unstable();
let m = row.len();
let mut max = 0;
for i in 0..m {
max = max.max(row[i] * (m - i) as i32);
}
max
}
}
#[test]
fn test() {
let matrix = vec_vec_i32![[0, 0, 1], [1, 1, 1], [1, 0, 1]];
let res = 4;
assert_eq!(Solution::largest_submatrix(matrix), res);
let matrix = vec_vec_i32![[1, 0, 1, 0, 1]];
let res = 3;
assert_eq!(Solution::largest_submatrix(matrix), res);
let matrix = vec_vec_i32![[1, 1, 0], [1, 0, 1]];
let res = 2;
assert_eq!(Solution::largest_submatrix(matrix), res);
let matrix = vec_vec_i32![[0, 0], [0, 0]];
let res = 0;
assert_eq!(Solution::largest_submatrix(matrix), res);
}