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])

All Problems

All Solutions