What is the main pattern to solve the Count Submatrices With All Ones problem?

The main pattern is state transition dynamic programming, where you preprocess each row into a `nums` array representing the count of consecutive ones.

How do you count submatrices in this problem?

Submatrices are counted by iterating through each row and using the `nums` array to determine the number of submatrices ending at each position.

What is the time complexity of solving Count 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.

Can this problem be optimized further?

Yes, the solution can be optimized using dynamic programming by avoiding brute-force submatrix counting and using row-wise preprocessing with the `nums` array.

What are some common mistakes when solving Count Submatrices With All Ones?

Common mistakes include not using dynamic programming for efficient row preprocessing and brute-forcing the submatrix counting process without optimizing with the `nums` array.

#1504

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

统计全 1 子矩形

给你一个 m x n 的二进制矩阵 mat ，请你返回有多少个子矩形的元素全部都是 1 。示例 1：输入： mat = [[1,0,1],[1,1,0],[1,1,0]] 输出： 13 解释：有 6 个 1x1 的矩形。有 2 个 1x2 的矩形。有 3 个 2x1 的矩形。有 1 …

数组动态规划栈矩阵单调栈

题目描述

给你一个 m x n 的二进制矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。

示例 1：

输入：mat = [[1,0,1],[1,1,0],[1,1,0]]
输出：13
解释：
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。

示例 2：

输入：mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
输出：24
解释：
有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。

提示：

1 <= m, n <= 150
mat[i][j] 仅包含 0 或 1

lightbulb

解题思路

方法一：枚举 + 前缀和

我们可以枚举矩阵的右下角 $(i, j)$ ，然后向上枚举矩阵的第一行 $k$ ，那么每一行以 $(i, j)$ 为右下角的矩阵的宽度就是 $\min_{k \leq i} \textit{g}[k][j]$ ，其中 $\textit{g}[k][j]$ 表示第 $k$ 行以 $(k, j)$ 为右下角的矩阵的宽度。

因此，我们可以预处理得到二维数组 $g[i][j]$ ，其中 $g[i][j]$ 表示第 $i$ 行中，从第 $j$ 列向左连续的 $1$ 的个数。

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        g = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if mat[i][j]:
                    g[i][j] = 1 if j == 0 else 1 + g[i][j - 1]
        ans = 0
        for i in range(m):
            for j in range(n):
                col = inf
                for k in range(i, -1, -1):
                    col = min(col, g[k][j])
                    ans += col
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should demonstrate familiarity with dynamic programming and matrix manipulation techniques.
question_mark
Look for a clear understanding of how to preprocess rows with the `nums` array to optimize the submatrix counting process.
question_mark
Expect the candidate to discuss time and space complexities in the context of dynamic programming and matrix traversal.

warning

常见陷阱

外企场景

error
Failing to optimize the solution by using the `nums` array can lead to inefficient brute-force counting.
error
Overlooking the need for row-wise preprocessing of the matrix, which can hinder performance in larger test cases.
error
Misunderstanding the role of dynamic programming and treating the problem as a straightforward iteration over all submatrices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
The problem can be generalized to non-binary matrices, where elements may have different values.
arrow_right_alt
A variant could involve considering rectangles instead of squares in submatrices.
arrow_right_alt
In a more challenging variant, you might be asked to find submatrices with a sum equal to a given target rather than all ones.

help

常见问题

外企场景

继续练习

#1526 形成目标数组的子数组最少增加次数 #2617 网格图中最少访问的格子数 #1130 叶值的最小代价生成树