Count Submatrices with Top-Left Element and Sum Less Than k solution and explanation
Google
9 more videos on this problem
Count Submatrices with Top-Left Element and Sum Less Than k | Brute Force | Optimal | Leetcode 3070codestorywithMIK · 27:26 · 7K views
3070. Count Submatrices with Top-Left Element and Sum Less Than k | Prefix SumAryan Mittal · 13:37 · 3K views
3070. Count Submatrices with Top-Left Element and Sum Less Than k | Leetcode Daily - PythonLeetcode Daily · 5:55 · 336 views
Daily Leetcode #2178: Mar 18, 2026 - 3070. Count Submatrices with Top-Left Element and Sum Less..Programming Live with Larry · 6:16 · 312 views
leetcode 3070 | Count Submatrices with Top-Left Element and Sum Less Than k |2D prefix|Leetcode POTDCode With Vick · 14:50 · 226 views
3070. Count Submatrices with Top-Left Element and Sum Less Than k (Leetcode Medium)Programming Live with Larry · 7:15 · 222 views
Count SubMatrices With Top-Left Element and Sum Less than K | Leetcode 3070 | Java HindiKernel Queen 👑 · 6:54 · 209 views
Count Submatrices with Top Left Element and Sum Less Than k | LeetCode 3070 - Pythonimpoldev · 11:32 · 152 views
Leetcode 3070: Count Submatrices with Top-Left Element and Sum Less Than kAlgorithms Casts · 13:53 · 147 views
Count Submatrices with Top-Left Element and Sum Less Than k | LeetCode 3070 | Java | Developer CoderDeveloper Coder · 12:38 · 126 views
The problem
You are given a 0-indexed integer matrix grid and an integer k.
Return the number of submatrices that contain the top-left element of the grid, and have a sum less than or equal to k.
Example 1:
Input: grid = [[7,6,3],[6,6,1]], k = 18 Output: 4 Explanation: 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 Explanation: 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.lengthn == grid[i].length1 <= n, m <= 10000 <= grid[i][j] <= 10001 <= k <= 109
Approach overview
Problem Overview: You are given a 2D grid of integers and a value k. Count how many submatrices start at the top-left corner (0,0) and have a total sum less than or equal to k. Each valid submatrix is defined by choosing any bottom-right cell and computing the sum of elements inside the rectangle from (0,0) to that cell.
Approach 1: Brute Force with Cumulative Prefix Sum (Time: O(m*n), Space: O(m*n))
The direct way to evaluate each candidate submatrix is to compute the sum of the rectangle ending at every cell. A prefix sum matrix makes this efficient. Build a 2D prefix array where prefix[i][j] stores the sum of the rectangle from (0,0) to (i,j). Once the table is built, every bottom-right cell instantly represents the sum of a submatrix whose top-left corner is fixed. Iterate through the grid, check whether prefix[i][j] <= k, and increment the count. This approach is simple and reliable because it converts repeated submatrix summations into constant-time lookups. It’s a common technique when working with cumulative sums in a matrix.
Approach 2: Optimized Summation with 1D Prefix Array (Time: O(m*n), Space: O(n))
You can reduce memory by avoiding the full 2D prefix table. Instead, maintain a running prefix while iterating row by row. Keep a 1D array where each index stores the cumulative column sum up to the current row. As you move across a row, maintain another running sum that represents the total rectangle sum from (0,0) to the current cell. Each step effectively reconstructs the same value that a 2D prefix table would provide, but with less space. If the running sum is less than or equal to k, increment the result. This approach works well because the rectangle always starts at the same origin, allowing incremental accumulation across rows and columns. It relies heavily on efficient traversal of a 2D array.
Recommended for interviews: Interviewers typically expect the prefix-sum insight. Showing the brute-force idea first demonstrates you understand the structure of submatrix sums. Transitioning to a prefix-sum solution proves you know how to eliminate repeated calculations and reduce the time per query to constant time. The optimized 1D variant is a good follow-up if memory usage becomes a concern.
Approach 1: Approach 1: Brute Force with Cumulative Prefix Sum
This approach leverages the cumulative prefix sum technique to quickly calculate the sum of submatrices starting from the top-left to any (i, j). The idea is to iterate through all possible submatrices starting at the top-left, using a prefix sum matrix to obtain the total sum efficiently. If the sum is less than or equal to k, we count it.
from typing import List
def countSubmatrices(grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
prefix = [[0] * n for _ in range(m)]
count = 0
for i in range(m):
for j in range(n):
prefix[i][j] = grid[i][j]
if i > 0:
prefix[i][j] += prefix[i-1][j]
if j > 0:
prefix[i][j] += prefix[i][j-1]
if i > 0 and j > 0:
prefix[i][j] -= prefix[i-1][j-1]
if prefix[i][j] <= k:
count += 1
return countpublic class Solution {
public int countSubmatrices(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
int[][] prefix = new int[m][n];
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
prefix[i][j] = grid[i][j];
if (i > 0) prefix[i][j] += prefix[i - 1][j];
if (j > 0) prefix[i][j] += prefix[i][j - 1];
if (i > 0 && j > 0) prefix[i][j] -= prefix[i - 1][j - 1];
if (prefix[i][j] <= k) count++;
}
}
return count;
}
}#include <vector>
using namespace std;
int countSubmatrices(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> prefix(m, vector<int>(n, 0));
int count = 0;
// Create prefix sum matrix
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
prefix[i][j] = grid[i][j];
if (i > 0) prefix[i][j] += prefix[i - 1][j];
if (j > 0) prefix[i][j] += prefix[i][j - 1];
if (i > 0 && j > 0) prefix[i][j] -= prefix[i - 1][j - 1];
if (prefix[i][j] <= k) count++;
}
}
return count;
}function countSubmatrices(grid, k) {
let m = grid.length, n = grid[0].length;
let prefix = Array.from({length: m}, () => Array(n).fill(0));
let count = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
prefix[i][j] = grid[i][j];
if (i > 0) prefix[i][j] += prefix[i - 1][j];
if (j > 0) prefix[i][j] += prefix[i][j - 1];
if (i > 0 && j > 0) prefix[i][j] -= prefix[i - 1][j - 1];
if (prefix[i][j] <= k) count++;
}
}
return count;
}#include <stdio.h>
int countSubmatrices(int** grid, int gridSize, int* gridColSize, int k) {
int i, j, r, c, count = 0;
int prefix[1001][1001] = {0};
prefix[0][0] = grid[0][0];
// Calculate prefix sum of each cell
for (i = 0; i < gridSize; ++i) {
for (j = 0; j < gridColSize[i]; ++j) {
prefix[i][j] = grid[i][j];
if (i > 0) prefix[i][j] += prefix[i-1][j];
if (j > 0) prefix[i][j] += prefix[i][j-1];
if (i > 0 && j > 0) prefix[i][j] -= prefix[i-1][j-1];
}
}
// Iterate over all possible submatrices including cell (0,0)
for (r = 0; r < gridSize; ++r) {
for (c = 0; c < gridColSize[r]; ++c) {
int submatrixSum = prefix[r][c];
if (submatrixSum <= k) count++;
}
}
return count;
}public class Solution {
public int CountSubmatrices(int[][] grid, int k) {
int m = grid.Length, n = grid[0].Length;
int[,] prefix = new int[m, n];
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
prefix[i, j] = grid[i][j];
if (i > 0) prefix[i, j] += prefix[i - 1, j];
if (j > 0) prefix[i, j] += prefix[i, j - 1];
if (i > 0 && j > 0) prefix[i, j] -= prefix[i - 1, j - 1];
if (prefix[i, j] <= k) count++;
}
}
return count;
}
}A Python implementation that creates a prefix sum grid to quickly compute submatrix sums with a single loop check to maintain the count of valid submatrices.
Time Complexity: O(m * n)
Space Complexity: O(m * n)
Approach 2: Approach 2: Optimized Summation with 1D Prefix Array
Instead of a full 2D prefix sum array, this approach uses a 1D prefix sum and iterative row expansion to calculate submatrix sums and maintain under k leveraging a sliding window or two-pointer technique.
def countSubmatrices(grid, k):
m, n = len(grid), len(grid[0])
count = 0
for start_row in range(m):
prefixRow = [0] * n
for row in range(start_row, m):
submatrix_sum = 0
for col in range(n):
prefixRow[col] += grid[row][col]
submatrix_sum += prefixRow[col]
if submatrix_sum <= k:
count += 1
return countpublic class Solution {
public int countSubmatrices(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
int count = 0;
int[] prefixRow = new int[n];
for (int startRow = 0; startRow < m; startRow++) {
java.util.Arrays.fill(prefixRow, 0);
for (int row = startRow; row < m; row++) {
int submatrixSum = 0;
for (int col = 0; col < n; col++) {
prefixRow[col] += grid[row][col];
submatrixSum += prefixRow[col];
if (submatrixSum <= k) count++;
}
}
}
return count;
}
}#include <vector>
using namespace std;
int countSubmatrices(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
int count = 0;
vector<int> prefixRow(n);
for (int startRow = 0; startRow < m; ++startRow) {
fill(prefixRow.begin(), prefixRow.end(), 0);
for (int row = startRow; row < m; ++row) {
int submatrixSum = 0;
for (int col = 0; col < n; ++col) {
prefixRow[col] += grid[row][col];
submatrixSum += prefixRow[col];
if (submatrixSum <= k) count++;
}
}
}
return count;
}function countSubmatrices(grid, k) {
let m = grid.length, n = grid[0].length;
let count = 0;
for (let startRow = 0; startRow < m; ++startRow) {
let prefixRow = Array(n).fill(0);
for (let row = startRow; row < m; ++row) {
let submatrixSum = 0;
for (let col = 0; col < n; ++col) {
prefixRow[col] += grid[row][col];
submatrixSum += prefixRow[col];
if (submatrixSum <= k) count++;
}
}
}
return count;
}#include <stdio.h>
int countSubmatrices(int** grid, int gridSize, int* gridColSize, int k) {
int i, j, r, count = 0;
int prefixRow[1000];
for (i = 0; i < gridSize; ++i) {
for (j = 0; j < 1000; ++j) prefixRow[j] = 0; // Resetting prefixRow
for (j = i; j >= 0; --j) {
int submatrixSum = 0;
for (r = 0; r < gridColSize[i]; ++r) {
prefixRow[r] += grid[j][r];
submatrixSum += prefixRow[r];
if (submatrixSum <= k) count++;
}
}
}
return count;
}public class Solution {
public int CountSubmatrices(int[][] grid, int k) {
int m = grid.Length, n = grid[0].Length;
int count = 0;
int[] prefixRow = new int[n];
for (int startRow = 0; startRow < m; startRow++) {
System.Array.Clear(prefixRow, 0, n);
for (int row = startRow; row < m; row++) {
int submatrixSum = 0;
for (int col = 0; col < n; col++) {
prefixRow[col] += grid[row][col];
submatrixSum += prefixRow[col];
if (submatrixSum <= k) count++;
}
}
}
return count;
}
}The Python solution achieves efficient evaluation of submatrix sums for a 1D dynamic prefix row approach, incrementing from each starting row iteratively while accounting for eligible submatrix constraints.
Time Complexity: O(m * n * n)
Space Complexity: O(n)
Approach 3: 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.
The calculation formula for the two-dimensional prefix sum is:
$
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + x
The time complexity is O(m times n), and the space complexity is O(m times n), where m and n$ are the number of rows and columns of the matrix, respectively.
function countSubmatrices(grid: number[][], k: number): number {
const m = grid.length;
const n = grid[0].length;
const s: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
let ans: number = 0;
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + grid[i - 1][j - 1];
if (s[i][j] <= k) {
++ans;
}
}
}
return ans;
}func countSubmatrices(grid [][]int, k int) (ans int) {
s := make([][]int, len(grid)+1)
for i := range s {
s[i] = make([]int, len(grid[0])+1)
}
for i, row := range grid {
for j, x := range row {
s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + x
if s[i+1][j+1] <= k {
ans++
}
}
}
return
}impl Solution {
pub fn count_submatrices(grid: Vec<Vec<i32>>, k: i32) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut s = vec![vec![0; n + 1]; m + 1];
let mut ans = 0;
for i in 1..=m {
for j in 1..=n {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + grid[i - 1][j - 1];
if s[i][j] <= k { ans += 1; }
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force with Cumulative Prefix Sum | Time Complexity: O(m * n) |
| Approach 2: Optimized Summation with 1D Prefix Array | Time Complexity: O(m * n * n) |
| Two-Dimensional Prefix Sum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with 2D Prefix Sum | O(m*n) | O(m*n) | Best for clarity and quick implementation when memory is not constrained |
| Optimized 1D Prefix Accumulation | O(m*n) | O(n) | Useful when reducing auxiliary memory while keeping linear traversal |
Frequently asked questions
Is Count Submatrices with Top-Left Element and Sum Less Than k easy or hard?
The problem is rated Medium because the main challenge is recognizing that every valid submatrix starts at the same top-left coordinate. Once you apply the prefix sum technique, the implementation becomes straightforward.
Count Submatrices with Top-Left Element and Sum Less Than k Python/Java solution
Python and Java implementations typically construct a prefix sum matrix and iterate through every cell to check if the cumulative value is within k. The algorithm runs in O(m*n) time and uses either a 2D prefix array or a memory-optimized 1D running sum.
How to solve Count Submatrices with Top-Left Element and Sum Less Than k in O(n)?
The problem cannot be solved in strictly O(n) for an m x n matrix because every cell must be examined. The optimal strategy achieves O(m*n) time by maintaining prefix sums so the sum of the rectangle ending at each cell is computed in constant time.
What is the best approach for Count Submatrices with Top-Left Element and Sum Less Than k?
The most practical approach uses a prefix sum technique. Build cumulative sums for the matrix so each cell quickly represents the sum of the rectangle from (0,0) to that position. Then iterate through all cells and count those whose prefix sum is less than or equal to k. This runs in O(m*n) time with O(m*n) space, or O(n) space with a 1D optimization.
Is Count Submatrices with Top-Left Element and Sum Less Than k asked at Google/Amazon/Meta?
Prefix sum and submatrix sum problems frequently appear in interviews at companies such as Google, Amazon, and Meta. Variants include counting submatrices with target sums or computing rectangle sums efficiently using prefix arrays.
What data structure is used in Count Submatrices with Top-Left Element and Sum Less Than k?
The main data structure is a prefix sum array (either 2D or compressed to 1D). It stores cumulative sums so that rectangle totals can be retrieved instantly without recomputing every element inside the submatrix.
What is the time complexity of Count Submatrices with Top-Left Element and Sum Less Than k?
The optimal solution runs in O(m*n) time where m is the number of rows and n is the number of columns. Each cell is processed once after prefix sums are computed. Space complexity is O(m*n) for a full 2D prefix matrix or O(n) when using a compressed 1D prefix array.