How do I ensure submatrices include the top-left element?

Always start your iteration from the first element grid[0][0] and extend bottom-right coordinates to cover candidate submatrices.

Can I solve this problem without prefix sums?

Technically yes, but brute-force will be too slow for large matrices; prefix sums enable O(1) submatrix sum queries.

What is the main pattern to recognize in this problem?

This problem follows the Array plus Matrix pattern where 2D cumulative sums optimize counting submatrices efficiently.

How does early termination improve performance?

Skipping further expansions when a submatrix sum exceeds k avoids unnecessary calculations and reduces iteration overhead.

What constraints should I watch for in large grids?

Ensure your algorithm handles up to 1000x1000 matrices and large k values without exceeding memory or time limits.

#3070

Medium

auto_awesome数组·matrix

LeetCode 题解工作台

元素和小于等于 k 的子矩阵的数目

给你一个下标从 0 开始的整数矩阵 grid 和一个整数 k 。返回包含 grid 左上角元素、元素和小于或等于 k 的子矩阵的数目。示例 1：输入： grid = [[7,6,3],[6,6,1]], k = 18 输出： 4 解释：如上图所示，只有 4 个子矩阵满足：包含 grid …

数组矩阵前缀和

题目描述

给你一个下标从 0 开始的整数矩阵 grid 和一个整数 k。

返回包含 grid 左上角元素、元素和小于或等于 k 的 子矩阵的数目。

示例 1：

输入：grid = [[7,6,3],[6,6,1]], k = 18
输出：4
解释：如上图所示，只有 4 个子矩阵满足：包含 grid 的左上角元素，并且元素和小于或等于 18 。

示例 2：

输入：grid = [[7,2,9],[1,5,0],[2,6,6]], k = 20
输出：6
解释：如上图所示，只有 6 个子矩阵满足：包含 grid 的左上角元素，并且元素和小于或等于 20 。

提示：

m == grid.length
n == grid[i].length
1 <= n, m <= 1000
0 <= grid[i][j] <= 1000
1 <= k <= 10⁹

lightbulb

解题思路

方法一：二维前缀和

题目实际上求的是二维矩阵有多少个和小于等于 $k$ 的前缀子矩阵。

二维前缀和的计算公式为：

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + x

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

1

2

3

4

5

6

7

8

9

10

class Solution:
    def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
        s = [[0] * (len(grid[0]) + 1) for _ in range(len(grid) + 1)]
        ans = 0
        for i, row in enumerate(grid, 1):
            for j, x in enumerate(row, 1):
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x
                ans += s[i][j] <= k
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on how many submatrices are considered and prefix sums are computed, potentially O(m _n) for building sums and O(m_ n) for counting. Space complexity is O(m*n) for the prefix sum matrix.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect questions about handling large matrices efficiently without brute-force scanning.
question_mark
Watch for prompts about early termination or skipping unnecessary submatrices.
question_mark
Be ready to explain prefix sum construction and submatrix sum calculation clearly.

warning

常见陷阱

外企场景

error
Forgetting that every submatrix must include the top-left element, not just any submatrix.
error
Not using prefix sums, leading to excessive time complexity and potential TLE.
error
Incorrect indexing when computing submatrix sums from the prefix sum array.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count submatrices with bottom-right element included instead of top-left, requiring reversed iteration.
arrow_right_alt
Find submatrices with sum exactly equal to k, needing precise sum matching.
arrow_right_alt
Limit submatrix size to fixed dimensions while still including top-left element.

help

常见问题

外企场景

继续练习

#3212 统计 X 和 Y 频数相等的子矩阵数量 #3225 网格图操作后的最大分数 #2906 构造乘积矩阵