1727. Largest Submatrix With Rearrangements

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.

1727. Largest Submatrix With Rearrangements
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);
}