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

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.