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.

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.

Description Solution Video 27:26

3070. Count Submatrices with Top-Left Element and Sum Less Than k

Q: 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.

Q: 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.

Medium74.8% acceptance2 companies

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.length
n == grid[i].length
1 <= n, m <= 1000
0 <= grid[i][j] <= 1000
1 <= k <= 10⁹

Asked at 2 companies

Barclays

Google

Topics

27:26

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[7,6,3],[6,6,1]]
18

Input

[[7,2,9],[1,5,0],[2,6,6]]
20

Your code is saved on this device.Solution