##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1183.html

# 1183. Maximum Number of Ones

Hard

## Description

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

## Solution

Starting from cell (0, 0), consider each square sub-matrix of size sideLength * sideLength. Use a 2D array counts to store the counts of each position of the square sub-matrix. For each i from 0 to height - 1 and for each j from 0 to width - 1, increase counts[i % sideLength][j % sideLength] by 1. Then use a priority queue to store all the elements in counts, where the maximum element is polled first. Poll maxOnes elements from the priority queue and calculate their sum, and return.

• class Solution {
public int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
int[][] counts = new int[sideLength][sideLength];
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++)
counts[i % sideLength][j % sideLength]++;
}
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer num1, Integer num2) {
return num2 - num1;
}
});
for (int i = 0; i < sideLength; i++) {
for (int j = 0; j < sideLength; j++)
priorityQueue.offer(counts[i][j]);
}
int maxTotalOnes = 0;
for (int i = 0; i < maxOnes; i++)
maxTotalOnes += priorityQueue.poll();
return maxTotalOnes;
}
}

• Todo

• class Solution:
def maximumNumberOfOnes(
self, width: int, height: int, sideLength: int, maxOnes: int
) -> int:
x = sideLength
cnt =  * (x * x)
for i in range(width):
for j in range(height):
k = (i % x) * x + (j % x)
cnt[k] += 1
cnt.sort(reverse=True)
return sum(cnt[:maxOnes])