Maximum Number of Ones

hard greedy matrix counting

Problem

Consider a matrix with width columns and height rows, where every cell holds a 0 or a 1, and any square sub-matrix of size sideLength × sideLength contains at most maxOnes ones. Return the maximum possible number of ones in the whole matrix.

Inputwidth = 5, height = 4, sideLength = 2, maxOnes = 1

Output6

Tiling 2×2 blocks across a 5×4 grid, template cell (0,0) repeats 3×2 = 6 times. With maxOnes = 1 we put a single 1 at that best cell of every block, for 6 ones total.

width

height

sideLength

maxOnes

def maximum_number_of_ones(width, height, side_length, max_ones):
    counts = []
    for r in range(side_length):
        for c in range(side_length):
            rows = (height - r + side_length - 1) // side_length
            cols = (width - c + side_length - 1) // side_length
            counts.append(rows * cols)
    counts.sort(reverse=True)
    return sum(counts[:max_ones])

function maximumNumberOfOnes(width, height, sideLength, maxOnes) {
  const counts = [];
  for (let r = 0; r < sideLength; r++) {
    for (let c = 0; c < sideLength; c++) {
      const rows = Math.ceil((height - r) / sideLength);
      const cols = Math.ceil((width - c) / sideLength);
      counts.push(rows * cols);
    }
  }
  counts.sort((a, b) => b - a);
  let total = 0;
  for (let k = 0; k < maxOnes; k++) total += counts[k];
  return total;
}

class Solution {
    public int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
        int[] counts = new int[sideLength * sideLength];
        int idx = 0;
        for (int r = 0; r < sideLength; r++) {
            for (int c = 0; c < sideLength; c++) {
                int rows = (height - r + sideLength - 1) / sideLength;
                int cols = (width - c + sideLength - 1) / sideLength;
                counts[idx++] = rows * cols;
            }
        }
        Arrays.sort(counts);
        int total = 0;
        for (int k = 0; k < maxOnes; k++) total += counts[counts.length - 1 - k];
        return total;
    }
}

int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
    vector<int> counts;
    for (int r = 0; r < sideLength; r++) {
        for (int c = 0; c < sideLength; c++) {
            int rows = (height - r + sideLength - 1) / sideLength;
            int cols = (width - c + sideLength - 1) / sideLength;
            counts.push_back(rows * cols);
        }
    }
    sort(counts.rbegin(), counts.rend());
    int total = 0;
    for (int k = 0; k < maxOnes; k++) total += counts[k];
    return total;
}

Explanation

The clever observation is that the whole grid behaves like a repeating tile of size sideLength × sideLength. Because every such square must look the same in terms of how many ones it can hold, a one placed at position (r, c) inside the tile shows up again at every copy of that tile across the grid.

So each of the sideLength² positions in the tile has a fixed repeat count — how many times that position appears in the full width × height grid. We compute that count with a simple ceiling division for the rows and columns it covers.

Since every tile may hold at most maxOnes ones, we want to place those ones at the positions that repeat the most. So we sort the repeat counts from high to low and add up the top maxOnes of them. That sum is the most ones the whole grid can contain.

This is greedy: filling the highest-frequency positions first gives the biggest payoff for each one we are allowed to place.

Example: width=5, height=4, sideLength=2, maxOnes=1. Position (0,0) repeats 3×2 = 6 times, the most of any cell. With only one allowed per block, we use that best cell, giving 6 ones.

Time: O(s² log s) Space: O(s²)