Largest submatrix with rearrangements

Array Greedy Sorting Matrix

75.2% acceptance

Feb 25, 2026

1978

107

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn largest_submatrix(mut matrix: Vec<Vec<i32>>) -> i32 {
    let m = matrix.len();
    let n = matrix[0].len();
    // Compute column heights
    for i in 1..m {
      for j in 0..n {
        if matrix[i][j] == 1 {
          matrix[i][j] += matrix[i - 1][j];
        }
      }
    }
    let mut ans = 0;
    for i in 0..m {
      let mut row = matrix[i].clone();
      row.sort_unstable_by(|a, b| b.cmp(a)); // sort descending
      for (j, &h) in row.iter().enumerate() {
        if h == 0 { break; }
        ans = ans.max(h * (j as i32 + 1));
      }
    }
    ans
  }
}