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 <= 1001 <= sideLength <= width, height0 <= maxOnes <= sideLength * sideLengthProblem 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.
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.
Python
Java
C++
Go
JavaScript
| Approach | Time | Space | When 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 + Sort | O(sideLength² log(sideLength²)) | O(sideLength²) | Simple implementation when sorting the frequency list is sufficient |
| Count Equivalent Positions + Max Heap | O(sideLength² log(sideLength²)) | O(sideLength²) | Preferred when selecting top maxOnes frequencies using a priority queue |
1183 Maximum Number of Ones • Kelvin Chandra • 2,546 views views
Watch 3 more video solutions →Practice Maximum Number of Ones with our built-in code editor and test cases.
Practice on FleetCode