Is Maximum Number of Ones easy or hard?

The problem is labeled Hard because the constraint seems to require checking many submatrices. The difficulty comes from spotting the repeating sideLength × sideLength pattern and converting the grid problem into a frequency counting and greedy selection task.

Maximum Number of Ones Python/Java solution

Implement the counting step for each index in the sideLength × sideLength block, compute its repetition frequency using ceiling division, and push it into a list or heap. Then sum the top maxOnes frequencies. The same logic works across Python, Java, C++, Go, and JavaScript.

What is the best approach for Maximum Number of Ones?

The optimal approach counts how often each position in a sideLength × sideLength base block appears in the full grid. Since every window allows at most maxOnes ones, select the maxOnes positions with the highest repetition counts. This greedy selection can be implemented using sorting or a max heap with time complexity O(sideLength² log(sideLength²)).

How to solve Maximum Number of Ones in O(s² log s²)?

Compute how many times each cell (i, j) in the sideLength × sideLength pattern repeats across the height × width grid. Store these frequencies, then choose the maxOnes largest values. Summing those frequencies gives the maximum number of ones possible while respecting the window constraint.

Is Maximum Number of Ones asked at Google/Amazon/Meta?

Grid optimization and pattern-repetition problems similar to Maximum Number of Ones appear in interviews at companies like Google and Amazon. The problem tests recognition of repeating structures, greedy selection, and efficient counting rather than brute-force simulation.

What data structure is used in Maximum Number of Ones?

The typical solution uses an array or list to store repetition frequencies and a max heap (priority queue) or sorting to pick the top maxOnes positions. The heap helps efficiently retrieve the largest frequency values.

What is the time complexity of Maximum Number of Ones?

The optimal solution runs in O(sideLength² log(sideLength²)) time and O(sideLength²) space. The algorithm computes repetition frequencies for each position in the base block and then selects the top maxOnes values using sorting or a heap.

Description Hints 4 Solution Video 5:16

1183. Maximum Number of Ones

Hard70.6% acceptance1 companyPremium elsewhere, free here

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

Asked at 1 company

Qualcomm

Topics

Greedy Heap (Priority Queue)

Hints open one at a time

Hint 1

Think of a greedy mathematical solution.

Hint 2

Say you choose to set some cell (i, j) to 1, all cells (x, y) such that i % sideLength == x % sideLength and j % sideLength == y % sideLength can also be set to 1 without increasing the max number of ones in a sub-matrix.

Hint 3

In one move, choose to set all the cells with some modulus (i % sideLength, j % sideLength) to 1.

Hint 4

Choose the cells with max frequency.

5:16

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

Input

Your code is saved on this device.Solution