Maximum Number of Ones

Hard · Heap / Priority Queue · Explanation and code example

Optimally Fill the Remainder Grids

How it works

Instead of computing and sorting all positions, we can directly calculate the answer by analyzing the structure of the tiled matrix. The matrix divides into regions based on how the sideLength pattern tiles:

  • Full tiles that appear (height / sideLength) * (width / sideLength) times.
  • Partial tiles along the right edge, bottom edge, and bottom-right corner.

Positions in the corner remainder region (bottom-right) appear the most frequently because they get counted in the main grid plus both edge strips plus the corner. We should fill these first, then the positions in the edge strips, prioritizing the edge with more repetitions.

Steps

  1. Start by placing maxOnes ones in the fully repeated grid sections, contributing maxOnes * (height / sideLength) * (width / sideLength) ones.
  2. Fill positions in the corner remainder region first (size = (height % sideLength) * (width % sideLength)). Each such position contributes to all three remainder regions plus the main grid.
  3. Based on which dimension has more full tiles, fill the appropriate edge strip next.
  4. Fill the remaining edge strip with any leftover positions.
  5. Return the total count.

Complexity

  • Time complexity: O(1)

  • Space complexity: O(1)

Things to watch for

Misunderstanding the Tiling Pattern

The constraint applies to every sideLength x sideLength submatrix, not just non-overlapping tiles. This means adjacent submatrices overlap, creating a repeating pattern where each position (r, c) in the pattern maps to the same relative position (r % sideLength, c % sideLength) across the entire matrix.

Incorrect Frequency Calculation

When calculating how many times a position in the pattern appears in the full matrix, you must account for partial tiles at the edges. The formula (1 + (width - c - 1) / sideLength) handles this, but off-by-one errors are common. Using (width - c) / sideLength or similar incorrect formulas will give wrong counts.

Swapping Width and Height

The problem distinguishes between width (columns) and height (rows). Confusing these dimensions when calculating horizontal and vertical repetitions leads to incorrect frequency counts, especially when the matrix is not square.

Greedy Selection Order

After computing frequencies, you must select the maxOnes positions with the highest frequencies. Forgetting to sort in descending order or selecting positions with lower frequencies will not maximize the total number of ones in the matrix.

Python code example

class Solution:
    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:
        answer = maxOnes * ((height // sideLength) * (width // sideLength))
        remain = maxOnes

        cnt1 = min((height % sideLength) * (width % sideLength), remain)
        answer += ((height // sideLength) + (width // sideLength) + 1) * cnt1
        remain -= cnt1

        if height // sideLength > width // sideLength:
            cnt2 = min(((width % sideLength) * sideLength) - ((height % sideLength) * (width % sideLength)), remain)
            answer += (height // sideLength) * cnt2
            remain -= cnt2
            cnt3 = min(((height % sideLength) * sideLength) - ((height % sideLength) * (width % sideLength)), remain)
            answer += (width // sideLength) * cnt3
            remain -= cnt3
        else:
            cnt2 = min(((height % sideLength) * sideLength) - ((height % sideLength) * (width % sideLength)), remain)
            answer += (width // sideLength) * cnt2
            remain -= cnt2
            cnt3 = min(((width % sideLength) * sideLength) - ((height % sideLength) * (width % sideLength)), remain)
            answer += (height // sideLength) * cnt3
            remain -= cnt3

        return answer

C++ code example

class Solution {
public:
    int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
        int answer = maxOnes * ((height / sideLength) * (width / sideLength));
        int remain = maxOnes;

        int cnt1 = min((height % sideLength) * (width % sideLength), remain);
        answer += ((height / sideLength) + (width / sideLength) + 1) * cnt1;
        remain -= cnt1;

        if (height / sideLength > width / sideLength) {
            int cnt2 = min(((width % sideLength) * sideLength) - ((height % sideLength) * (width % sideLength)), remain);
            answer += (height / sideLength) * cnt2;
            remain -= cnt2;

            int cnt3 = min(((height % sideLength) * sideLength) - ((height % sideLength) * (width % sideLength)), remain);
            answer += (width / sideLength) * cnt3;
            remain -= cnt3;
        } else {
            int cnt2 = min(((height % sideLength) * sideLength) - ((height % sideLength) * (width % sideLength)), remain);
            answer += (width / sideLength) * cnt2;
            remain -= cnt2;

            int cnt3 = min(((width % sideLength) * sideLength) - ((height % sideLength) * (width % sideLength)), remain);
            answer += (height / sideLength) * cnt3;
            remain -= cnt3;
        }

        return answer;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations