⚡Flashcard Drill➔
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

  1. 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).
  2. The transition is dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) when the cell is 1, otherwise 0.
  3. Summing dp over all cells counts every square exactly once.
  4. 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 0 and 1, 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems