⚡Flashcard Drill➔
NeetCode #898LC-1183HardMath & GeometryNC Algo100
← Back to All Problems

#898 · #1183 · Maximum Number of Ones(矩阵中 1 的最大数量)

📌 Problem Statement & Constraints

You are given the dimensions width and height of a binary matrix, a window size sideLength, and maxOnes. Place ones so that every sideLength x sideLength submatrix contains at most maxOnes ones, and return the maximum possible total number of ones. Constraints: 1 <= width, height <= 10^9, 1 <= sideLength <= min(width, height), 0 <= maxOnes <= sideLength^2.

💡 Core Algorithmic Approaches

  1. Any valid arrangement is periodic with period sideLength in both axes: sliding a window by sideLength covers exactly the same residue classes, so the constraint is unchanged.
  2. The problem therefore reduces to choosing which cells of one sideLength x sideLength tile hold ones, subject to selecting at most maxOnes of them.
  3. A tile cell (i, j) is replicated ceil((width - i) / sideLength) * ceil((height - j) / sideLength) times in the full matrix, written with integer arithmetic as ((width - i - 1) // sideLength + 1) * ((height - j - 1) // sideLength + 1).
  4. To maximise the total, pick the maxOnes tile cells with the largest replication counts and sum those counts.
  5. A refinement worth noting: the row factor and the column factor each take at most two distinct values across the tile, so the four distinct products can be combined in O(1) without enumerating the whole tile.

💻 Benchmark Python3 Implementation

class Solution:
    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:
        counts = []
        for i in range(sideLength):
            for j in range(sideLength):
                # how many times cell (i, j) of the tile appears in the matrix
                rows = (width - i - 1) // sideLength + 1
                cols = (height - j - 1) // sideLength + 1
                counts.append(rows * cols)
        counts.sort(reverse=True)
        return sum(counts[:maxOnes])

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(L^2 log L) where L = sideLength: enumerate the tile and sort its replication counts.
💾 Space Complexity
O(L^2): the list of replication counts for one tile.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting that a window can be partially outside the matrix: the replication count uses ceiling division, which is exactly the (x - 1) // L + 1 form.
  • Choosing tile cells by position rather than by count: the correct choice is simply the maxOnes largest replication counts, not a geometric pattern.
  • Sorting ascending: the largest counts are wanted, so a descending sort is required.
  • Assuming the tile enumeration is always cheap: it costs O(L^2), so for very large sideLength the O(1) two-value-factor grouping described in the approach is the way to go.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems