Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1183.html
1183. Maximum Number of Ones
Level
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 = [0] * (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])