Maximum number of ones

Math Greedy Sorting Heap (Priority Queue)

70.6% acceptance

Mar 31, 2026

173

Consider a matrix M with dimensions width * height, such that every cell has value 0 or 1, and any square sub-matrix of M of size sideLength * sideLength has at most maxOnes ones. Return the maximum possible number of ones that the matrix M can have.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_number_of_ones(width: i32, height: i32, side_length: i32, max_ones: i32) -> i32 {
    let s = side_length as usize;
    // For each position (r % s, c % s) in the tile, count how many cells map to it
    let mut counts = Vec::with_capacity(s * s);
    for r in 0..s {
      for c in 0..s {
        let rows = (height as usize - r + s - 1) / s;
        let cols = (width as usize - c + s - 1) / s;
        counts.push(rows * cols);
      }
    }
    counts.sort_unstable_by(|a, b| b.cmp(a));
    counts[..max_ones as usize].iter().sum::<usize>() as i32
  }
}