Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 1183 with 20 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 1183 # by problem number
lcpy gen -s maximum_number_of_ones # by problem name
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.
Input: width = 3, height = 3, sideLength = 2, maxOnes = 1
Output: 4
Input: width = 3, height = 3, sideLength = 2, maxOnes = 2
Output: 6
class Solution:
# Time: O(width * height)
# Space: O(sideLength^2)
def maximum_number_of_ones(
self, width: int, height: int, side_length: int, max_ones: int
) -> int:
x = side_length
counts = [0] * (x * x)
for i in range(width):
for j in range(height):
counts[(i % x) * x + (j % x)] += 1
counts.sort(reverse=True)
return sum(counts[:max_ones])
| Time | Space |
|---|---|
| O(width * height) | O(sideLength^2) |