What is the key idea behind solving the Count Square Submatrices with All Ones problem?

The key idea is to use dynamic programming to calculate the size of the largest square submatrix ending at each position in the matrix and sum these values.

How can space complexity be optimized in this problem?

Space complexity can be optimized by reducing the 2D DP table to a 1D array, maintaining only the current and previous rows of the matrix.

What are the edge cases to consider in this problem?

Edge cases include matrices with no ones (resulting in 0 squares), and matrices where all elements are 1 (resulting in the maximum number of square submatrices).

How does the dynamic programming approach work in the Count Square Submatrices with All Ones problem?

The dynamic programming approach builds a table where each entry represents the side length of the largest square that can be formed with its bottom-right corner at that element, iterating through the matrix to accumulate the total number of square submatrices.

What is the time complexity of the solution for Count Square Submatrices with All Ones?

The time complexity is O(m * n), where m is the number of rows and n is the number of columns in the matrix, as we need to iterate through each element once.

#1277

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

统计全为 1 的正方形子矩阵

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1 ，请你统计并返回其中完全由 1 组成的正方形子矩阵的个数。示例 1：输入： matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] 输出： 15 解释：边长为 1 的正方形有 10 个。边长为…

数组动态规划矩阵

题目描述

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

示例 1：

输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释： 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

示例 2：

输入：matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。 
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.

提示：

1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 为以 $(i,j)$ 为右下角的正方形子矩阵的边长，初始时 $f[i][j] = 0$ ，答案为 $\sum_{i,j} f[i][j]$ 。

考虑 $f[i][j]$ 如何进行状态转移。

当 $\text{matrix}[i][j] = 0$ 时，有 $f[i][j] = 0$ 。
当 $\text{matrix}[i][j] = 1$ $matrix [i] [j] = 1$ 时，状态 $f[i][j]$ $f [i] [j]$ 的值取决于其上、左、左上三个位置的值：
- 如果 $i = 0$ 或 $j = 0$ ，则 $f[i][j] = 1$ 。
- 否则 $f[i][j] = \min(f[i-1][j-1], f[i-1][j], f[i][j-1]) + 1$ 。

答案为 $\sum_{i,j} f[i][j]$ 。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别为矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        f = [[0] * n for _ in range(m)]
        ans = 0
        for i, row in enumerate(matrix):
            for j, v in enumerate(row):
                if v == 0:
                    continue
                if i == 0 or j == 0:
                    f[i][j] = 1
                else:
                    f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1]) + 1
                ans += f[i][j]
        return ans

speed

复杂度分析

指标	值
时间	O(row \cdot col)
空间	O(col)

psychology

面试官常问的追问

外企场景

question_mark
The candidate should demonstrate understanding of dynamic programming and how state transition works in this context.
question_mark
Look for awareness of space optimization techniques, particularly reducing a 2D DP table to 1D.
question_mark
The ability to handle edge cases, such as matrices with no ones or matrices that are very large, will indicate strong problem-solving skills.

warning

常见陷阱

外企场景

error
Misunderstanding the recurrence relation and incorrectly calculating the DP values.
error
Failing to optimize space complexity, leading to excessive memory usage.
error
Not summing the values in the DP table correctly to count the total number of square submatrices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Matrix with larger dimensions (e.g., 500x500) to test efficiency and space optimization.
arrow_right_alt
Matrix where all elements are 1, which will test if the DP approach can correctly count all possible submatrices.
arrow_right_alt
Matrix with random placements of 1's and 0's to ensure robustness of the solution under various configurations.

help

常见问题

外企场景

继续练习

#1289 下降路径最小和 II #1301 最大得分的路径数目 #1349 参加考试的最大学生数