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