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

Description

You are given a 0-indexed integer matrix grid and an integer k.

Return the number of 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 <= 109

 

Solutions

Solution: Prefix Sum

• Time complexity: O(mn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number}
 */
const countSubmatrices = function (grid, k) {
  const m = grid.length;
  const n = grid[0].length;
  let preRowSum = Array.from({ length: n }, () => 0);
  let result = 0;

  for (let row = 0; row < m; row++) {
    const currentRow = new Array(n).fill(0);

    for (let col = 0; col < n; col++) {
      const value = grid[row][col];
      const topSum = preRowSum[col];
      const leftSum = currentRow[col - 1] ?? 0;
      const cornerSum = preRowSum[col - 1] ?? 0;
      const sum = value + topSum + leftSum - cornerSum;

      currentRow[col] = sum;

      if (sum <= k) {
        result += 1;
      }
    }

    preRowSum = currentRow;
  }

  return result;
};