LeetCode 3070 - Count Submatrices with Top-Left Element and Sum Less Than k
The problem gives us a 2D integer matrix called grid and an integer k. We need to count how many submatrices satisfy two conditions: 1. The submatrix must contain the top-left cell of the original matrix, which is grid[0][0]. 2.
Difficulty: 🟡 Medium
Topics: Array, Matrix, Prefix Sum
Solution
Problem Understanding
The problem gives us a 2D integer matrix called grid and an integer k. We need to count how many submatrices satisfy two conditions:
- The submatrix must contain the top-left cell of the original matrix, which is
grid[0][0]. - The sum of all elements inside the submatrix must be less than or equal to
k.
Because every valid submatrix must include the top-left element, every valid submatrix is uniquely determined by choosing a bottom-right corner (r, c). The top-left corner is always fixed at (0, 0).
That means every candidate submatrix looks like this:
- Rows from
0tor - Columns from
0toc
So instead of considering arbitrary submatrices, we only need to evaluate prefix-style rectangles.
The input matrix dimensions are:
m == grid.lengthn == grid[i].length
Both m and n can be as large as 1000, which means the matrix can contain up to 1,000,000 cells. This immediately tells us that expensive nested computations over submatrices will likely be too slow.
The values inside the matrix are non-negative:
0 <= grid[i][j] <= 1000
This is an important property because prefix sums become especially effective when values are non-negative and cumulative totals only increase.
The expected output is a single integer representing the number of valid submatrices whose sum is at most k.
Several edge cases are important:
- A
1 x 1matrix, where there is only one possible submatrix. - Cases where every submatrix exceeds
k. - Cases where every submatrix is valid.
- Large matrices, where recomputing sums repeatedly would be prohibitively expensive.
- Matrices containing zeros, where many different rectangles may share the same sum.
Approaches
Brute Force Approach
A straightforward solution is to generate every possible submatrix that starts at (0, 0) and compute its sum manually.
Since the top-left corner is fixed, we only need to iterate over every possible bottom-right corner (r, c).
For each (r, c):
- Traverse all cells from
(0, 0)to(r, c) - Compute the total sum
- Check whether the sum is less than or equal to
k
This approach is correct because it explicitly evaluates every valid candidate submatrix.
However, it is extremely inefficient.
There are m * n possible bottom-right corners, and each sum computation may scan up to m * n cells again.
This produces a worst-case complexity of:
O(m^2 * n^2)
With matrix dimensions up to 1000 x 1000, this is far too slow.
Optimal Approach
The key observation is that every valid submatrix is actually a prefix rectangle starting at (0, 0).
This makes 2D prefix sums a perfect fit.
A 2D prefix sum allows us to compute the sum of any rectangle in constant time after preprocessing.
In this problem, we can simplify even further. Since every rectangle starts at (0, 0), the prefix sum at position (r, c) already equals the sum of the required submatrix.
So instead of separately building and querying a prefix matrix, we can compute the prefix sums directly in-place while iterating through the matrix.
For each cell (r, c):
prefix[r][c] =
grid[r][c]
+ prefix[r-1][c]
+ prefix[r][c-1]
- prefix[r-1][c-1]
This gives the sum of the rectangle from (0, 0) to (r, c).
If that value is at most k, we increment the answer.
Because each cell is processed once, the solution runs efficiently in linear time relative to the matrix size.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(m² × n²) | O(1) | Recomputes each submatrix sum repeatedly |
| Optimal | O(m × n) | O(1) extra space | Uses in-place 2D prefix sums |
Algorithm Walkthrough
- Initialize a counter called
answerto0. - Traverse the matrix row by row and column by column.
- For each cell
(r, c), convert the original value into a 2D prefix sum.
The value at (r, c) should represent the total sum of the rectangle from (0, 0) to (r, c).
We use the standard inclusion-exclusion formula:
current =
grid[r][c]
+ top
+ left
- topLeft
Where:
top = grid[r-1][c]ifr > 0left = grid[r][c-1]ifc > 0topLeft = grid[r-1][c-1]if both exist
- Store the computed prefix sum back into
grid[r][c].
This avoids allocating another matrix and keeps the extra space constant.
5. Check whether the prefix sum is less than or equal to k.
If it is, increment answer.
6. Continue until all cells have been processed.
7. Return answer.
Why it works
The algorithm maintains the invariant that after processing cell (r, c), grid[r][c] equals the sum of all elements inside the rectangle from (0, 0) to (r, c).
Since every valid submatrix in the problem must begin at (0, 0), every possible candidate corresponds exactly to one prefix sum cell.
Therefore, counting how many prefix sums are at most k is equivalent to counting the required submatrices.
Python Solution
from typing import List
class Solution:
def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
rows = len(grid)
cols = len(grid[0])
answer = 0
for r in range(rows):
for c in range(cols):
top = grid[r - 1][c] if r > 0 else 0
left = grid[r][c - 1] if c > 0 else 0
top_left = grid[r - 1][c - 1] if r > 0 and c > 0 else 0
grid[r][c] = grid[r][c] + top + left - top_left
if grid[r][c] <= k:
answer += 1
return answer
The implementation follows the exact algorithm described earlier.
First, we determine the matrix dimensions and initialize the result counter.
The nested loops iterate through every cell once. At each position, we gather the previously computed prefix sums from the top, left, and top-left neighbors.
The inclusion-exclusion formula ensures that overlapping regions are counted correctly:
topadds the rectangle aboveleftadds the rectangle to the lefttop_leftis subtracted because it was added twice
The computed value replaces the original cell value. After this update, grid[r][c] becomes the sum of the rectangle from (0, 0) to (r, c).
Whenever this prefix sum is at most k, we increment the answer.
Because the matrix itself stores prefix sums, we avoid allocating another 2D array.
Go Solution
func countSubmatrices(grid [][]int, k int) int {
rows := len(grid)
cols := len(grid[0])
answer := 0
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
top := 0
left := 0
topLeft := 0
if r > 0 {
top = grid[r-1][c]
}
if c > 0 {
left = grid[r][c-1]
}
if r > 0 && c > 0 {
topLeft = grid[r-1][c-1]
}
grid[r][c] = grid[r][c] + top + left - topLeft
if grid[r][c] <= k {
answer++
}
}
}
return answer
}
The Go implementation mirrors the Python solution closely.
One important difference is that Go requires explicit variable declarations and boundary checks.
The constraints guarantee that all sums fit safely inside Go's int type on standard LeetCode environments, since the maximum possible sum is:
1000 * 1000 * 1000 = 10^9
which fits comfortably within 32-bit signed integer range.
The solution updates the input matrix in place exactly like the Python version, so no additional 2D allocation is required.
Worked Examples
Example 1
Input:
grid = [
[7, 6, 3],
[6, 6, 1]
]
k = 18
We process cells row by row.
Step-by-step Prefix Sum Construction
| Cell | Computation | Prefix Sum | Valid? |
|---|---|---|---|
| (0,0) | 7 | 7 | Yes |
| (0,1) | 6 + 7 | 13 | Yes |
| (0,2) | 3 + 13 | 16 | Yes |
| (1,0) | 6 + 7 | 13 | Yes |
| (1,1) | 6 + 13 + 13 - 7 | 25 | No |
| (1,2) | 1 + 16 + 25 - 13 | 29 | No |
Valid prefix sums:
7, 13, 16, 13
Total valid submatrices:
4
Example 2
Input:
grid = [
[7, 2, 9],
[1, 5, 0],
[2, 6, 6]
]
k = 20
Step-by-step Prefix Sum Construction
| Cell | Computation | Prefix Sum | Valid? |
|---|---|---|---|
| (0,0) | 7 | 7 | Yes |
| (0,1) | 2 + 7 | 9 | Yes |
| (0,2) | 9 + 9 | 18 | Yes |
| (1,0) | 1 + 7 | 8 | Yes |
| (1,1) | 5 + 9 + 8 - 7 | 15 | Yes |
| (1,2) | 0 + 18 + 15 - 9 | 24 | No |
| (2,0) | 2 + 8 | 10 | Yes |
| (2,1) | 6 + 15 + 10 - 8 | 23 | No |
| (2,2) | 6 + 24 + 23 - 15 | 38 | No |
Valid prefix sums:
7, 9, 18, 8, 15, 10
Total valid submatrices:
6
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(m × n) | Every cell is processed exactly once |
| Space | O(1) extra space | Prefix sums are stored directly inside the input matrix |
The algorithm performs constant work for each matrix cell. Since there are m * n cells, the total runtime is linear in the size of the matrix.
No additional 2D structures are allocated. Aside from a few scalar variables, all computations reuse the original matrix storage.
Test Cases
from typing import List
class Solution:
def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
rows = len(grid)
cols = len(grid[0])
answer = 0
for r in range(rows):
for c in range(cols):
top = grid[r - 1][c] if r > 0 else 0
left = grid[r][c - 1] if c > 0 else 0
top_left = grid[r - 1][c - 1] if r > 0 and c > 0 else 0
grid[r][c] = grid[r][c] + top + left - top_left
if grid[r][c] <= k:
answer += 1
return answer
solver = Solution()
# Example 1
assert solver.countSubmatrices([[7,6,3],[6,6,1]], 18) == 4
# Example 2
assert solver.countSubmatrices([[7,2,9],[1,5,0],[2,6,6]], 20) == 6
# Single cell valid
assert solver.countSubmatrices([[5]], 5) == 1
# Single cell invalid
assert solver.countSubmatrices([[10]], 5) == 0
# All zeros
assert solver.countSubmatrices([[0,0],[0,0]], 0) == 4
# Entire matrix valid
assert solver.countSubmatrices([[1,1],[1,1]], 10) == 4
# Only first cell valid
assert solver.countSubmatrices([[1,100],[100,100]], 1) == 1
# One row matrix
assert solver.countSubmatrices([[1,2,3,4]], 6) == 3
# One column matrix
assert solver.countSubmatrices([[1],[2],[3]], 3) == 2
# Large values near limit
assert solver.countSubmatrices([[1000,1000],[1000,1000]], 4000) == 4
# Mixed values
assert solver.countSubmatrices([[2,1],[3,4]], 6) == 3
Test Summary
| Test | Why |
|---|---|
[[7,6,3],[6,6,1]], k=18 |
Validates official example |
[[7,2,9],[1,5,0],[2,6,6]], k=20 |
Validates larger official example |
[[5]], k=5 |
Smallest valid matrix |
[[10]], k=5 |
Smallest invalid matrix |
[[0,0],[0,0]], k=0 |
Ensures zero sums work correctly |
[[1,1],[1,1]], k=10 |
Every submatrix valid |
[[1,100],[100,100]], k=1 |
Only one valid prefix rectangle |
[[1,2,3,4]], k=6 |
Single row handling |
[[1],[2],[3]], k=3 |
Single column handling |
[[1000,1000],[1000,1000]], k=4000 |
Large values near constraint limits |
[[2,1],[3,4]], k=6 |
Mixed valid and invalid cases |
Edge Cases
Single Cell Matrix
A 1 x 1 matrix is the smallest possible input. There is only one possible submatrix, the matrix itself.
A buggy implementation might incorrectly assume neighboring prefix values exist or mishandle boundary checks.
This solution handles the case safely because it explicitly checks whether r > 0 and c > 0 before accessing neighboring cells.
All Prefix Sums Exceed k
Consider a matrix where even the smallest rectangle already exceeds k.
For example:
grid = [[10]]
k = 5
An incorrect solution might accidentally count invalid rectangles due to initialization mistakes.
This implementation checks every computed prefix sum directly against k before incrementing the answer, so invalid rectangles are never counted.
Single Row or Single Column
Matrices with only one row or one column are common sources of indexing bugs because one dimension never has neighbors.
For example:
[[1,2,3,4]]
or
[[1],[2],[3]]
The implementation handles these correctly because missing neighbors contribute 0 to the prefix sum formula.
Matrices Containing Zeros
Zero values can create many rectangles with identical sums.
For example:
[[0,0],
[0,0]]
Every prefix rectangle has sum 0.
The algorithm correctly counts all of them because each prefix sum is computed independently and compared against k without assumptions about strictly increasing totals.