Daily LeetCode - by Vítor Belim

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⁹

/** * @param {number[][]} grid * @param {number} k * @return {number} */ var countSubmatrices = function(grid, k) { const m = grid.length; const n = grid[0].length; let res = 0; for (let row = 0; row < m; row++) { for (let col = 0; col < n; col++) { const top = row > 0 ? grid[row - 1][col] : 0; const left = col > 0 ? grid[row][col - 1] : 0; const diag = row > 0 && col > 0 ? grid[row - 1][col - 1] : 0; grid[row][col] += top + left - diag; if (grid[row][col] <= k) { res++; } } } return res; };

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

Description

Solutions

Description

Solutions

AI Explanation