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;
    }
}

All Problems

All Solutions