Code Implementation

class Solution:
    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:
        from collections import Counter
        freq = Counter()
        for i in range(sideLength):
            for j in range(sideLength):
                # Count how many times each position in the sideLength x sideLength block appears
                freq[(i, j)] = ((height - i + sideLength - 1) // sideLength) * ((width - j + sideLength - 1) // sideLength)
        # Take the maxOnes positions with the largest frequency
        return sum(cnt for _, cnt in sorted(freq.items(), key=lambda x: -x[1])[:maxOnes])
      

class Solution {
public:
    int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
        vector<int> freq;
        for (int i = 0; i < sideLength; ++i) {
            for (int j = 0; j < sideLength; ++j) {
                int count = ((height - i + sideLength - 1) / sideLength) * ((width - j + sideLength - 1) / sideLength);
                freq.push_back(count);
            }
        }
        sort(freq.begin(), freq.end(), greater<int>());
        int res = 0;
        for (int i = 0; i < maxOnes; ++i) {
            res += freq[i];
        }
        return res;
    }
};
      

class Solution {
    public int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
        List<Integer> freq = new ArrayList<>();
        for (int i = 0; i < sideLength; i++) {
            for (int j = 0; j < sideLength; j++) {
                int count = ((height - i + sideLength - 1) / sideLength) * ((width - j + sideLength - 1) / sideLength);
                freq.add(count);
            }
        }
        Collections.sort(freq, Collections.reverseOrder());
        int res = 0;
        for (int i = 0; i < maxOnes; i++) {
            res += freq.get(i);
        }
        return res;
    }
}
      

var maximumNumberOfOnes = function(width, height, sideLength, maxOnes) {
    let freq = [];
    for (let i = 0; i < sideLength; i++) {
        for (let j = 0; j < sideLength; j++) {
            let count = Math.floor((height - i + sideLength - 1) / sideLength) * Math.floor((width - j + sideLength - 1) / sideLength);
            freq.push(count);
        }
    }
    freq.sort((a, b) => b - a);
    let res = 0;
    for (let i = 0; i < maxOnes; i++) {
        res += freq[i];
    }
    return res;
};
      

Problem Description

• For every sideLength x sideLength sub-square of the matrix, there are at most maxOnes ones in that square.

• Each sideLength x sideLength sub-square must have at most maxOnes ones.
• Each cell can be either 0 or 1.
• You must maximize the total number of ones in the whole matrix.

Thought Process

Solution Approach

1. Block Decomposition:
   • Divide the matrix into sideLength x sideLength blocks. The pattern in each block will repeat throughout the matrix.
2. Frequency Calculation:
   • For each position (i, j) in the block, calculate how many times it will appear in the overall matrix. This is determined by how many times the block "fits" across the width and height.
3. Greedy Placement:
   • Sort all positions in the block by their frequency (i.e., how many times they appear in the matrix).
   • Select the maxOnes most frequent positions and set them to 1 in the block pattern.
4. Total Ones Calculation:
   • The total number of ones in the matrix is the sum of frequencies of these selected positions.

Example Walkthrough

• The block is 2x2. There are 4 positions: (0,0), (0,1), (1,0), (1,1).
• For each position, calculate how many times it appears in the 3x3 matrix:
• (0,0): appears in all 4 possible 2x2 sub-squares (top-left, top-right, bottom-left, bottom-right) → frequency = 4
• Other positions also appear 4 times each.
• All positions have the same frequency. We can pick any 2 positions (since maxOnes = 2).
• Total ones = 4 (frequency) * 2 (positions) = 8.

1. Calculate frequencies for each block position.
2. Pick the top 2 positions.
3. Sum their frequencies for the answer.

Time and Space Complexity

• Brute-force Approach:
  • Would require checking all possible assignments of ones and zeros, which is exponential in the number of cells — O(2^{width \times height}).
• Optimized Approach (as above):
  • We only consider the sideLength x sideLength block, which is at most 400 positions (if sideLength=20).
  • For each block position, we compute its frequency in O(1).
  • Sorting the frequencies takes O(sideLength^2 \log sideLength^2).
  • Overall time complexity: O(sideLength^2 \log sideLength^2).
  • Space complexity: O(sideLength^2) for storing frequencies.

Summary