HardNo. 1183LeetCode Premium
Maximum Number of Ones — LeetCode 1183 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Greedy, Math, Sorting, Heap (Priority Queue)
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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
- 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.
Python solution
class Solution:
def maximumNumberOfOnes(
self, width: int, height: int, sideLength: int, maxOnes: int
) -> int:
x = sideLength
cnt = [0] * (x * x)
for i in range(width):
for j in range(height):
k = (i % x) * x + (j % x)
cnt[k] += 1
cnt.sort(reverse=True)
return sum(cnt[:maxOnes])Complexity
- Time
- O(m × n)where m and n are the number of rows and columns of the matrix, respectively
- Space · auxiliary
- O(1) to O(n)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1183. Maximum Number of Ones is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1686 | Stone Game VI | Medium |
| 0502 | IPO | Hard |
| 0630 | Course Schedule III | Hard |
| 0857 | Minimum Cost to Hire K Workers | Hard |
| 0910 | Smallest Range II | Medium |
| 0976 | Largest Perimeter Triangle | Easy |
Frequently asked questions
- How hard is LeetCode 1183. Maximum Number of Ones?
LeetCode 1183. Maximum Number of Ones is rated Hard on LeetCode.
- What topics does LeetCode 1183. Maximum Number of Ones cover?
LeetCode 1183. Maximum Number of Ones is tagged Greedy, Math, Sorting and Heap (Priority Queue) on LeetCode.
- Is LeetCode 1183. Maximum Number of Ones a premium problem?
Yes. LeetCode 1183. Maximum Number of Ones is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.