Count Submatrices with Top-Left Element and Sum Less Than k
Source: leetcode
Difficulty: Medium
Tags: array, matrix, prefix-sum

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:**


![](https://assets.leetcode.com/uploads/2024/01/01/example1.png)

```

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:**


![](https://assets.leetcode.com/uploads/2024/01/01/example21.png)

```

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`




C++ solution:
class Solution {
public:
    int countSubmatrices(vector<vector<int>>& grid, int k) {
        int count = 0;
        for (int i = 0; i < grid.size(); i++)
            for (int j = 1; j < grid[0].size(); j++)
                grid[i][j] += grid[i][j-1];

        for (int i = 1; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                grid[i][j] += grid[i-1][j];
                count += grid[i][j] <= k;
            }
        }

        for (int j = 0; j < grid[0].size(); j++)
            count += grid[0][j] <= k;

        return count;
    }
};

auto init = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 'c';
}();

Go solution:
func countSubmatrices(grid [][]int, k int) int {
    n := len(grid)
	m := len(grid[0])

	res := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			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]
			}
			if grid[i][j] <= k {
				res++
			}
		}
	}
	return res
}

Java solution:
class Solution {
    public int countSubmatrices(int[][] grid, int k) {
        int row = grid.length;
        int col = grid[0].length;
        int res = 0;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                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];

                if (grid[i][j] <= k)
                    res++;
                else
                    break;
            }
        }

        return res;
    }
}

JavaScript solution:
function countSubmatrices(grid, k) {
    let count = 0
    
    for (let row = 0; row < grid.length; row++) {
        let sum = 0
        for (let col = 0; col < grid[row].length; col++) {
            const prevRowValue = row - 1 >= 0 ? grid[row - 1][col] : 0
            sum += grid[row][col] + prevRowValue
            grid[row][col] = grid[row][col] + prevRowValue
            
            if (sum <= k) count++
        }
    }
    
    return count
}

Python solution:
class Solution:

	def _rotate_matrix(self, matrix: list[list[int]], k: int):
		for m in zip(*matrix[::-1]):
			yield list(accumulate(m[::-1]))

	def countSubmatrices(self, grid: list[list[int]], k: int) -> int:
		grid_sum = [list(accumulate(g)) for g in grid]

		res = 0
		for g in self._rotate_matrix(grid_sum, 3):
			res += bisect_right(g, k)
		return res

Ruby solution:
def count_submatrices(grid, k)
    m = grid.size
    n = grid[0].size
    grid2 = (0...m).map{ [0]*n }
    m.times{ |j|
        s=0
        n.times{ |i|
            s+=grid[j][i]
            grid2[j][i]=s
    }}
    cnt = 0
    n.times{ |i|
        s=0
        m.times{ |j|
            s+=grid2[j][i]
            s<=k ? cnt+=1 : break
    }}
    cnt
end