Skip to main content
Talentd

Maximum Number of Ones - Solution & Explanation

HardPremiumFree on FleetCodeGreedyHeap (Priority Queue)7 min readAsked at: Qualcomm
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You have a height × width binary matrix. Every sideLength × sideLength submatrix can contain at most maxOnes ones. The goal is to place ones in the grid so the total number of ones is maximized without violating this constraint.

Approach 1: Direct Grid Construction (Brute Force) (Time: O(height × width × sideLength²), Space: O(1))

A naive strategy tries to greedily place 1s in the grid while checking every affected sideLength × sideLength submatrix. For each placement, you scan nearby windows and verify the constraint. This works for small grids but quickly becomes expensive because every candidate cell can trigger multiple submatrix checks. The method mainly helps build intuition: each placement affects several overlapping windows, which makes the constraint hard to maintain directly.

Approach 2: Count Equivalent Positions (Greedy + Heap) (Time: O(sideLength² log(sideLength²)), Space: O(sideLength²))

The key observation: the grid repeats every sideLength rows and columns. Any cell (r, c) behaves the same as (r % sideLength, c % sideLength) inside every sliding window. Instead of reasoning about the entire grid, you only analyze the sideLength × sideLength base pattern. For each position in this pattern, count how many times it appears in the full grid using repeated offsets. Some positions appear more frequently than others depending on how many rows and columns remain.

Each position contributes a frequency equal to the number of times it repeats in the full matrix. Since every sideLength × sideLength window can contain at most maxOnes ones, you can choose at most maxOnes positions in this base pattern to set to 1. To maximize the total ones in the full grid, select the positions with the highest repetition counts. Sort the frequencies or push them into a max heap (priority queue) and pick the top maxOnes. This greedy selection guarantees the largest total contribution.

This solution converts a grid optimization problem into selecting the most valuable repeating cells. It uses a simple counting step followed by a greedy selection with a greedy strategy and optionally a heap.

Recommended for interviews: The counting of equivalent positions is the expected solution. Interviewers want to see the pattern-repetition insight and the greedy selection of the highest-frequency cells. Mentioning the brute-force idea shows you understand the constraint mechanics, but recognizing the repeating block and reducing the search space to sideLength² cells demonstrates stronger problem-solving skill.

Solution

For convenience, let's denote x = sideLength.

Consider a x times x square, we need to select at most maxOnes points inside the square and set them to 1. Note that when the point at coordinate (i, j) is selected, all points at coordinates (i\pm k_1 times x, j\pm k_2 times x) can be equivalently set to 1. Therefore, we calculate the number of equivalent positions of the coordinate (i, j) in the matrix, and select the top maxOnes with the most quantities.

The time complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively.

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Grid Construction (Brute Force)O(height × width × sideLength²)O(1)Conceptual approach to understand how overlapping submatrices enforce the constraint
Count Equivalent Positions + SortO(sideLength² log(sideLength²))O(sideLength²)Simple implementation when sorting the frequency list is sufficient
Count Equivalent Positions + Max HeapO(sideLength² log(sideLength²))O(sideLength²)Preferred when selecting top maxOnes frequencies using a priority queue

Video Solution

1183 Maximum Number of Ones • Kelvin Chandra • 2,603 views views

Watch 3 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Maximum Number of Ones with our built-in code editor and test cases.

Practice on FleetCode
Previous

Container With Most Water

Next

Wildcard Matching