LeetCode Problem 1183

Difficulty: 🔴 Hard
Topics: Math, Greedy, Sorting, Heap (Priority Queue)

Solution

LeetCode 1183, Maximum Number of Ones

Problem Understanding

The problem gives us a binary matrix M with dimensions height x width. Every cell in the matrix must contain either 0 or 1.

There is one important restriction:

Every square submatrix of size sideLength x sideLength may contain at most maxOnes cells equal to 1.

Our goal is to construct such a matrix while maximizing the total number of ones in the entire matrix.

In other words, we want to place as many 1s as possible globally, while ensuring that every local sideLength x sideLength window respects the limit.

The output is the maximum number of ones achievable under these constraints.

The constraints are relatively small:

• width, height <= 100
• sideLength <= 100

This tells us that polynomial solutions are acceptable, but brute force over all matrices is impossible because the number of binary matrices is exponential.

The key challenge is understanding how the local restriction on every square submatrix affects the global arrangement of ones.

Several edge cases are important:

• maxOnes = 0, every cell must be zero.
• sideLength = 1, every individual cell forms a submatrix, so the entire matrix can contain at most maxOnes ones per cell.
• maxOnes = sideLength * sideLength, there is effectively no restriction, so the whole matrix can be filled with ones.
• Non-square dimensions such as width = 100, height = 1, where repetition patterns behave differently.
• Very small matrices where the repeating pattern partially overlaps the matrix boundary.

Approaches

Brute Force Approach

A naive approach would attempt to try all possible binary matrices and verify whether every sideLength x sideLength submatrix satisfies the condition.

For each matrix:

1. Enumerate every possible sideLength x sideLength window.
2. Count the number of ones inside it.
3. Reject the matrix if any window exceeds maxOnes.
4. Otherwise, count the total ones and keep the maximum.

This approach is correct because it explicitly checks every valid configuration.

However, it is computationally impossible. A matrix with width * height cells has:

$$2^{(width \cdot height)}$$

possible configurations.

Even a 10 x 10 matrix would already have:

$$2^{100}$$

possibilities, which is completely infeasible.

We need a structural observation that avoids exploring individual matrices.

Key Insight

The crucial observation is that the restriction depends only on positions modulo sideLength.

Consider a repeating pattern of size:

$$sideLength \times sideLength$$

Any cell (r, c) belongs to pattern position:

$$(r \bmod sideLength,\ c \bmod sideLength)$$

Every sideLength x sideLength submatrix contains exactly one occurrence of every pattern position.

That means:

• If we choose some positions inside the base pattern to be 1,
• Then repeating that pattern across the matrix guarantees that every sideLength x sideLength square contains exactly that many ones.

Therefore:

• We only need to choose at most maxOnes positions inside the base pattern.
• Different pattern positions appear different numbers of times in the full matrix.
• To maximize total ones, we should choose the positions that repeat most frequently.

So the problem becomes:

1. Compute how many times each pattern position appears in the matrix.
2. Select the maxOnes largest frequencies.
3. Sum them.

This transforms a difficult combinatorial optimization problem into a counting and sorting problem.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^(width*height))	O(width*height)	Tries every binary matrix
Optimal	O(sideLength² log(sideLength²))	O(sideLength²)	Counts repeating frequencies and chooses the best positions

Algorithm Walkthrough

Step 1, Understand the repeating pattern

Any cell (r, c) can be mapped into a base pattern position:

$$(r \bmod sideLength,\ c \bmod sideLength)$$

There are exactly:

$$sideLength^2$$

distinct pattern positions.

Every sideLength x sideLength submatrix contains one copy of each pattern position.

Therefore, if we place k ones inside the base pattern, every valid square will also contain exactly k ones.

So we may choose at most maxOnes positions in the base pattern.

Step 2, Count frequency of each pattern position

For each pattern row r:

$$rowCount = \left\lfloor \frac{height}{sideLength} \right\rfloor$$

plus one extra occurrence if the remainder covers that row.

Similarly for each pattern column c:

$$colCount = \left\lfloor \frac{width}{sideLength} \right\rfloor$$

plus one extra occurrence if the remainder covers that column.

The total number of appearances for position (r, c) is:

$$rowCount \times colCount$$

This tells us how many matrix cells become 1 if we choose that pattern position.

Step 3, Store all frequencies

We compute frequencies for all:

$$sideLength^2$$

positions and store them in a list.

Step 4, Choose the largest frequencies

Since we may activate only maxOnes positions, we sort frequencies in descending order and take the largest maxOnes values.

Step 5, Return the sum

The sum of the selected frequencies equals the maximum number of ones possible in the matrix.

Why it works

Every sideLength x sideLength submatrix contains exactly one copy of each modulo position. Therefore, choosing a set of modulo positions uniquely determines how many ones each square contains.

Because every chosen position contributes independently to the total number of ones, the optimal strategy is greedy: always choose the positions with the largest repetition counts.

This guarantees the maximum global number of ones while respecting the local constraint.

Python Solution

class Solution:
    def maximumNumberOfOnes(
        self,
        width: int,
        height: int,
        sideLength: int,
        maxOnes: int
    ) -> int:

        frequencies = []

        for r in range(sideLength):
            row_count = height // sideLength
            if r < height % sideLength:
                row_count += 1

            for c in range(sideLength):
                col_count = width // sideLength
                if c < width % sideLength:
                    col_count += 1

                frequencies.append(row_count * col_count)

        frequencies.sort(reverse=True)

        return sum(frequencies[:maxOnes])

The implementation directly follows the mathematical observation.

The outer loops iterate over every position inside the base sideLength x sideLength pattern.

For each row position, we compute how many actual matrix rows map to that modulo class. The same logic applies for columns.

Multiplying these counts gives the number of matrix cells represented by that pattern position.

All frequencies are collected into a list and sorted in descending order. Since we can select at most maxOnes pattern positions, the optimal answer is simply the sum of the largest maxOnes frequencies.

The implementation is concise because the problem reduces cleanly to counting repetitions.

Go Solution

package main

import "sort"

func maximumNumberOfOnes(width int, height int, sideLength int, maxOnes int) int {
	frequencies := []int{}

	for r := 0; r < sideLength; r++ {
		rowCount := height / sideLength
		if r < height%sideLength {
			rowCount++
		}

		for c := 0; c < sideLength; c++ {
			colCount := width / sideLength
			if c < width%sideLength {
				colCount++
			}

			frequencies = append(frequencies, rowCount*colCount)
		}
	}

	sort.Sort(sort.Reverse(sort.IntSlice(frequencies)))

	answer := 0

	for i := 0; i < maxOnes; i++ {
		answer += frequencies[i]
	}

	return answer
}

The Go implementation mirrors the Python solution closely.

The main difference is that Go requires explicit slice management and sorting utilities from the sort package.

Integer overflow is not a concern because the maximum possible answer is:

$$100 \times 100 = 10000$$

which easily fits inside Go's int type.

Worked Examples

Example 1

Input:
width = 3
height = 3
sideLength = 2
maxOnes = 1

Step 1, Base pattern positions

The repeating pattern is:

(0,0) (0,1)
(1,0) (1,1)

Step 2, Count frequencies

For rows:

height = 3
sideLength = 2

base count = 3 // 2 = 1
remainder = 1

So:

Pattern Row	Occurrences
0	2
1	1

For columns:

Pattern Column	Occurrences
0	2
1	1

Now compute frequencies:

Position	Frequency
(0,0)	2 × 2 = 4
(0,1)	2 × 1 = 2
(1,0)	1 × 2 = 2
(1,1)	1 × 1 = 1

Frequency list:

[4, 2, 2, 1]

Step 3, Choose largest maxOnes frequencies

maxOnes = 1

Take largest value:

4

Final answer:

4

Example 2

Input:
width = 3
height = 3
sideLength = 2
maxOnes = 2

The same frequencies apply:

[4, 2, 2, 1]

Now choose the two largest values:

4 + 2 = 6

Final answer:

6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(sideLength² log(sideLength²))	We compute all frequencies and sort them
Space	O(sideLength²)	We store all pattern frequencies

The dominant operation is sorting the frequency list. The list contains exactly:

$$sideLength^2$$

elements.

Since sideLength <= 100, the largest possible list has only 10000 elements, which is very manageable.

Test Cases

class Solution:
    def maximumNumberOfOnes(self, width, height, sideLength, maxOnes):
        frequencies = []

        for r in range(sideLength):
            row_count = height // sideLength
            if r < height % sideLength:
                row_count += 1

            for c in range(sideLength):
                col_count = width // sideLength
                if c < width % sideLength:
                    col_count += 1

                frequencies.append(row_count * col_count)

        frequencies.sort(reverse=True)

        return sum(frequencies[:maxOnes])

sol = Solution()

assert sol.maximumNumberOfOnes(3, 3, 2, 1) == 4  # example 1
assert sol.maximumNumberOfOnes(3, 3, 2, 2) == 6  # example 2

assert sol.maximumNumberOfOnes(1, 1, 1, 1) == 1  # single cell matrix
assert sol.maximumNumberOfOnes(1, 1, 1, 0) == 0  # no ones allowed

assert sol.maximumNumberOfOnes(5, 5, 1, 1) == 25  # every cell can be one

assert sol.maximumNumberOfOnes(4, 4, 2, 4) == 16  # unrestricted 2x2 pattern

assert sol.maximumNumberOfOnes(7, 5, 3, 0) == 0  # maxOnes is zero

assert sol.maximumNumberOfOnes(100, 100, 10, 100) == 10000  # entire matrix filled

assert sol.maximumNumberOfOnes(2, 3, 2, 1) == 2  # rectangular matrix

assert sol.maximumNumberOfOnes(8, 9, 3, 2) == 18  # uneven repetition counts

assert sol.maximumNumberOfOnes(6, 6, 3, 1) == 4  # choose best repeating position

Test Summary

Test	Why
(3,3,2,1)	Verifies example 1
(3,3,2,2)	Verifies example 2
(1,1,1,1)	Smallest non-empty matrix
(1,1,1,0)	No ones allowed
(5,5,1,1)	Every cell independently allowed
(4,4,2,4)	Entire pattern may be filled
(7,5,3,0)	Edge case with zero allowed ones
(100,100,10,100)	Maximum dimensions
(2,3,2,1)	Non-square matrix
(8,9,3,2)	Uneven modulo frequencies
(6,6,3,1)	Tests greedy frequency selection

Edge Cases

maxOnes equals zero

If maxOnes = 0, then no sideLength x sideLength square may contain any ones. Since every matrix cell belongs to some such square, the entire matrix must be zero.

A buggy implementation might still attempt to select frequencies or accidentally include one position. This implementation handles the case naturally because:

sum(frequencies[:0])

correctly evaluates to 0.

sideLength equals one

When sideLength = 1, every individual cell forms a 1 x 1 submatrix.

This means:

• If maxOnes = 0, all cells must be zero.
• If maxOnes = 1, all cells may be one.

This case is easy to mishandle conceptually because the repeating pattern contains only one position. The modulo counting logic still works correctly because every cell maps to the same pattern coordinate.

Matrix dimensions not divisible by sideLength

Consider:

width = 8
height = 9
sideLength = 3

Some modulo positions occur more frequently than others because the matrix does not divide evenly into repeating blocks.

A naive implementation might assume every pattern position appears equally often, which would produce incorrect answers.

This implementation carefully computes:

height // sideLength
height % sideLength

and similarly for columns, ensuring that extra rows and columns are distributed correctly among the earliest modulo classes.