#3070

Medium

LeetCode Problem Workspace

Count Submatrices with Top-Left Element and Sum Less Than k

Count all submatrices including the top-left element with sum less than k using array and matrix prefix sum strategies.

Problem Statement

Given a 0-indexed integer matrix grid of size m x n and an integer k, determine the total number of submatrices that include the top-left element grid[0][0] and whose sums do not exceed k. Each submatrix must start anywhere in the grid but must include the first element in its top-left corner calculation.

Return the count of all valid submatrices that satisfy these conditions. For example, for grid = [[7,6,3],[6,6,1]] and k = 18, the result is 4. Constraints: 1 <= m,n <= 1000, 0 <= grid[i][j] <= 1000, 1 <= k <= 10^9.

Examples

Example 1

Input: grid = [[7,6,3],[6,6,1]], k = 18

Output: 4

There are only 4 submatrices, shown in the image above, that contain the top-left element of grid, and have a sum less than or equal to 18.

Example 2

Input: grid = [[7,2,9],[1,5,0],[2,6,6]], k = 20

Output: 6

There are only 6 submatrices, shown in the image above, that contain the top-left element of grid, and have a sum less than or equal to 20.

Constraints

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

Solution Approach

Prefix Sum Matrix Construction

Compute a prefix sum matrix to quickly calculate any submatrix sum including the top-left element. This avoids repeated summing and ensures O(1) retrieval for each candidate submatrix sum during iteration.

Iterate Through Submatrices Efficiently

Loop over all possible bottom-right coordinates that include the top-left element. Use the prefix sum to compute submatrix sums and increment the count when the sum is less than or equal to k. This leverages the array plus matrix pattern for bounded iteration.

Optimize by Early Termination

If a submatrix sum exceeds k, skip further expansions in that direction to reduce unnecessary calculations. This exploits the monotonicity of sums along rows and columns when starting from the top-left element.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Two-Dimensional Prefix Sum

The problem is actually asking for the number of prefix submatrices in a two-dimensional matrix whose sum is less than or equal to $k$.

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#3212 count submatrices with equal frequency of x and y #3225 maximum score from grid operations #2906 construct product matrix