NeetCode #728LC-1277Medium2-D Dynamic Programming
← Back to All Problems#728 · #1277 · Count Square Submatrices with All Ones(统计全为 1 的正方形子矩阵)
📌 Problem Statement & Constraints
Given an
m x n binary matrix of 0 and 1, return the number of square submatrices that contain only 1s. Constraints: 1 <= m, n <= 300, and matrix[i][j] is 0 or 1.💡 Core Algorithmic Approaches
dp[i][j]is the side length of the largest all-ones square ending at(i, j), which also equals the number of all-ones squares whose bottom-right corner is(i, j).- The transition is
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])when the cell is1, otherwise 0. - Summing
dpover all cells counts every square exactly once. - The same rolling-row trick as Maximal Square keeps the space at O(n).
💻 Benchmark Python3 Implementation
class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
dp = [0] * (n + 1)
total = 0
for i in range(1, m + 1):
prev = 0
for j in range(1, n + 1):
tmp = dp[j]
if matrix[i - 1][j - 1] == 1:
dp[j] = 1 + min(dp[j], dp[j - 1], prev)
total += dp[j] # dp[j] squares end at this cell
else:
dp[j] = 0
prev = tmp
return total⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n): one pass.
💾 Space Complexity
O(n): a rolling row.
⚠️ Interview Pitfalls & Follow-ups
- Returning the largest square instead of the count:
dp[i][j]is both the side length and the number of squares ending there, and the answer is their sum. - Forgetting to zero blocked cells: stale values from the previous row would inflate the count.
- Taking the minimum of only two neighbours: all three of up, left, and diagonal are required.
- Mixing up integer and string cells: this problem uses integer
0and1, unlike Maximal Square which uses characters.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.