Count Submatrices with Top-Left Element and Sum Less Than k
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to iterate through every possible submatrix that starts at the top-left corner (0, 0). A submatrix is defined by its bottom-right corner (r, c). We can iterate through all possible r and c, and for each, we calculate the sum of the corresponding submatrix by iterating through all its elements. If the sum is less than or equal to k, we increment a counter.
Algorithm
- Initialize a counter
countto 0. - Iterate through each possible row
rfrom0tom-1(wheremis the number of rows). - Inside this loop, iterate through each possible column
cfrom0ton-1(wherenis the number of columns). - Each pair
(r, c)defines the bottom-right corner of a submatrix starting at(0, 0). - For each submatrix, calculate its sum by iterating from row
i = 0torand columnj = 0tocand addinggrid[i][j]to acurrentSum. - If
currentSumis less than or equal tok, incrementcount. - After all loops complete, return
count.
Walkthrough
This method uses a brute-force strategy. It considers every possible bottom-right corner (r, c) for a submatrix that must include the top-left element (0, 0). For each of these m * n potential submatrices, it calculates the sum by iterating over all the cells within that submatrix's bounds. This leads to recalculating sums of smaller submatrices multiple times.
For example, when calculating the sum for the submatrix ending at (r, c), we re-sum all the elements that were already part of the submatrix ending at (r, c-1).
class Solution { public int countSubmatrices(int[][] grid, int k) { int m = grid.length; int n = grid[0].length; int count = 0; // Iterate through all possible bottom-right corners (r, c) for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { // Calculate the sum of the submatrix from (0,0) to (r,c) long currentSum = 0; for (int i = 0; i <= r; i++) { for (int j = 0; j <= c; j++) { currentSum += grid[i][j]; } } // Check if the sum is within the limit if (currentSum <= k) { count++; } } } return count; }}Complexity
Time
O(m^2 * n^2), where `m` is the number of rows and `n` is the number of columns. For each of the `m*n` possible bottom-right corners, we iterate up to `m*n` elements to calculate the sum.
Space
O(1), as we only use a few variables to store the count and the current sum, not dependent on the input size.
Trade-offs
Pros
Simple to understand and implement.
Uses minimal extra space.
Cons
Highly inefficient due to nested loops.
Will result in a 'Time Limit Exceeded' error for the given constraints.
Solutions
Solution
class Solution {public int countSubmatrices(int[][] grid, int k) { int m = grid.length, n = grid[0].length; int[][] s = new int[m + 1][n + 1]; int ans = 0; for (int i = 1; i <= m; ++i) { for (int 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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.