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.
To avoid the redundant calculations of the brute-force approach, we can use a technique called 2D prefix sums. We precompute the sums of all submatrices starting at (0, 0) and store them in an auxiliary matrix. The sum of a submatrix with its bottom-right corner at (r, c) can then be retrieved in O(1) time.
Algorithm
- Create an auxiliary 2D array
prefixSumof size(m+1) x (n+1). - Populate the
prefixSummatrix. For each cell(i, j)in the original grid,prefixSum[i+1][j+1]is calculated using the formula:prefixSum[i+1][j+1] = grid[i][j] + prefixSum[i][j+1] + prefixSum[i+1][j] - prefixSum[i][j]. - Initialize a counter
countto 0. - Iterate through the
prefixSummatrix from(1, 1)to(m, n). - For each cell
(i, j), the valueprefixSum[i][j]represents the sum of the submatrix from(0,0)to(i-1, j-1). - If
prefixSum[i][j] <= k, incrementcount. - Return
count.
Walkthrough
This approach significantly improves performance by building a 2D prefix sum matrix. Let's call it prefixSum. The cell prefixSum[i][j] will store the sum of all elements in the rectangle from (0, 0) to (i-1, j-1) in the original grid. This matrix can be built in a single pass over the grid.
Once the prefixSum matrix is constructed, we can simply iterate through it. Each entry prefixSum[r+1][c+1] directly gives us the sum of the submatrix we are interested in (the one with bottom-right corner (r, c)). We check if this sum is less than or equal to k and update our count accordingly.
class Solution { public int countSubmatrices(int[][] grid, int k) { int m = grid.length; int n = grid[0].length; // prefixSum[i][j] stores the sum of submatrix from (0,0) to (i-1, j-1) int[][] prefixSum = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { prefixSum[i][j] = grid[i - 1][j - 1] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1]; } } int count = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (prefixSum[i][j] <= k) { count++; } } } return count; }}Complexity
Time
O(m * n). Building the prefix sum matrix takes O(m * n), and iterating through it to count valid submatrices also takes O(m * n). The total complexity is linear with respect to the number of cells in the grid.
Space
O(m * n) to store the auxiliary `prefixSum` matrix.
Trade-offs
Pros
Efficient time complexity, suitable for the given constraints.
Conceptually clean separation of precomputation and counting.
Cons
Requires extra space proportional to the size of the input grid.
This approach is a space-optimized version of the 2D Prefix Sum method. Instead of creating a new matrix to store prefix sums, we can modify the input grid in-place. The cell grid[i][j] is updated to hold the sum of the submatrix from (0, 0) to (i, j). This achieves the same time efficiency as the previous approach but with constant extra space.
Algorithm
- Initialize
countto 0. - Iterate through the grid with row
ifrom0tom-1and columnjfrom0ton-1. - In each iteration, update
grid[i][j]to store the prefix sum of the submatrix ending at(i, j). - The update rule is:
grid[i][j] += grid[i-1][j](ifi>0),grid[i][j] += grid[i][j-1](ifj>0), andgrid[i][j] -= grid[i-1][j-1](ifi>0andj>0). - After updating
grid[i][j], check if its new value is less than or equal tok. - If
grid[i][j] <= k, incrementcount. - After the loops finish, return
count.
Walkthrough
We can achieve optimal space complexity by recognizing that the prefix sum for grid[i][j] only depends on the values in the row above and the column to the left, which have already been converted to prefix sums in our traversal order. Therefore, we can overwrite the input grid with its prefix sums.
We iterate through each cell of the grid. For each cell (i, j), we calculate its prefix sum using the already computed prefix sums of its neighbors: grid[i-1][j], grid[i][j-1], and grid[i-1][j-1]. Immediately after computing the prefix sum for (i, j), we check if it's less than or equal to k and update our count. This combines the computation and counting steps into a single pass.
class Solution { public int countSubmatrices(int[][] grid, int k) { int m = grid.length; int n = grid[0].length; int count = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // Calculate prefix sum for grid[i][j] in-place if (i > 0) { grid[i][j] += grid[i - 1][j]; } if (j > 0) { grid[i][j] += grid[i][j - 1]; } if (i > 0 && j > 0) { grid[i][j] -= grid[i - 1][j - 1]; } // Check if the sum is within the limit if (grid[i][j] <= k) { count++; } } } return count; }}Complexity
Time
O(m * n). We iterate through each cell of the grid exactly once, performing constant time operations for each cell.
Space
O(1), as no additional data structures proportional to the input size are used. This assumes that modifying the input grid is acceptable.
Trade-offs
Pros
Optimal time complexity of O(m * n).
Optimal space complexity of O(1) (if input modification is allowed).
Cons
Modifies the original input grid, which might be an undesirable side effect in some contexts.
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; }}class Solution {public: int countSubmatrices(vector<vector<int>> &grid, int k) { int m = grid.size(), n = grid[0].size(); int s[m + 1][n + 1]; memset(s, 0, sizeof(s)); 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; }};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 ansVideo 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.