> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Maximum Number of Ones Python Solution

> Tested Python solution for LeetCode 1183 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 1183, [Hard](/catalog/hard). Topics: [Math](/catalog/topics/math), [Greedy](/catalog/topics/greedy), [Sorting](/catalog/topics/sorting), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue). [View on LeetCode](https://leetcode.com/problems/maximum-number-of-ones/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1183   # by problem number
lcpy gen -s maximum_number_of_ones   # by problem name
```

## 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.

### Examples

```
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]

```
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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/maximum_number_of_ones/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/maximum_number_of_ones/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
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])
```

## Complexity

| Time | Space |
| - | - |
| O(width \* height) | O(sideLength^2) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.