1183. Maximum Number of Ones

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.

 

Example 1:

Input: width = 3, height = 3, sideLength = 2, maxOnes = 1
Output: 4
Explanation:
In a 3*3 matrix, no 2*2 sub-matrix can have more than 1 one.
The best solution that has 4 ones is:
[1,0,1]
[0,0,0]
[1,0,1]

Example 2:

Input: width = 3, height = 3, sideLength = 2, maxOnes = 2
Output: 6
Explanation:
[1,0,1]
[1,0,1]
[1,0,1]

 

Constraints:

  • 1 <= width, height <= 100
  • 1 <= sideLength <= width, height
  • 0 <= maxOnes <= sideLength * sideLength

Rust Solution

struct Solution;
use std::cmp::Reverse;
use std::collections::BinaryHeap;

impl Solution {
    fn maximum_number_of_ones(width: i32, height: i32, side_length: i32, max_ones: i32) -> i32 {
        let width = width as usize;
        let height = height as usize;
        let side_length = side_length as usize;
        let max_ones = max_ones as usize;
        let mut queue: BinaryHeap<Reverse<usize>> = BinaryHeap::new();
        for i in 0..side_length {
            for j in 0..side_length {
                let rows = 1 + (height - (i + 1)) / side_length;
                let cols = 1 + (width - (j + 1)) / side_length;
                queue.push(Reverse(rows * cols));
                if queue.len() > max_ones {
                    queue.pop();
                }
            }
        }
        queue.into_iter().map(|t| t.0).sum::<usize>() as i32
    }
}

#[test]
fn test() {
    let width = 3;
    let height = 3;
    let side_length = 2;
    let max_ones = 1;
    let res = 4;
    assert_eq!(
        Solution::maximum_number_of_ones(width, height, side_length, max_ones),
        res
    );
    let width = 3;
    let height = 3;
    let side_length = 2;
    let max_ones = 2;
    let res = 6;
    assert_eq!(
        Solution::maximum_number_of_ones(width, height, side_length, max_ones),
        res
    );
}

Having problems with this solution? Click here to submit an issue on github.