Solution

Method 1 – Prefix Sum Brute Force

Intuition

We want to count all submatrices that start at the top-left (0,0) and end at (i,j) for all i, j, such that the sum of the submatrix is less than or equal to k. By precomputing prefix sums, we can quickly get the sum of any such submatrix.

Approach

Compute a prefix sum matrix where each cell (i, j) contains the sum of the submatrix from (0,0) to (i,j).
For every possible bottom-right corner (i, j), calculate the sum of the submatrix from (0,0) to (i,j) using the prefix sum.
If the sum is less than or equal to k, increment the answer.
Return the total count.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int countSubmatrices(vector<vector<int>>& grid, int k) {\n        int n = grid.size(), m = grid[0].size(), ans = 0;\n        vector<vector<int>> ps(n+1, vector<int>(m+1));\n        for (int i = 1; i <= n; ++i) {\n            for (int j = 1; j <= m; ++j) {\n                ps[i][j] = grid[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];\n                if (ps[i][j] <= k) ans++;\n            }\n        }\n        return ans;\n    }\n};","lang":"cpp"},{"language":"Go","code":"type Solution struct{}\nfunc (Solution) CountSubmatrices(grid [][]int, k int) int {\n    n, m := len(grid), len(grid[0])\n    ps := make([][]int, n+1)\n    for i := range ps {\n        ps[i] = make([]int, m+1)\n    }\n    ans := 0\n    for i := 1; i <= n; i++ {\n        for j := 1; j <= m; j++ {\n            ps[i][j] = grid[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1]\n            if ps[i][j] <= k {\n                ans++\n            }\n        }\n    }\n    return ans\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public int countSubmatrices(int[][] grid, int k) {\n        int n = grid.length, m = grid[0].length, ans = 0;\n        int[][] ps = new int[n+1][m+1];\n        for (int i = 1; i <= n; ++i) {\n            for (int j = 1; j <= m; ++j) {\n                ps[i][j] = grid[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];\n                if (ps[i][j] <= k) ans++;\n            }\n        }\n        return ans;\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun countSubmatrices(grid: Array<IntArray>, k: Int): Int {\n        val n = grid.size\n        val m = grid[0].size\n        val ps = Array(n+1) { IntArray(m+1) }\n        var ans = 0\n        for (i in 1..n) {\n            for (j in 1..m) {\n                ps[i][j] = grid[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1]\n                if (ps[i][j] <= k) ans++\n            }\n        }\n        return ans\n    }\n}","lang":"kotlin"},{"language":"Python","code":"class Solution:\n    def countSubmatrices(self, grid: list[list[int]], k: int) -> int:\n        n, m = len(grid), len(grid[0])\n        ps = [[0]*(m+1) for _ in range(n+1)]\n        ans = 0\n        for i in range(1, n+1):\n            for j in range(1, m+1):\n                ps[i][j] = grid[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1]\n                if ps[i][j] <= k:\n                    ans += 1\n        return ans","lang":"python"},{"language":"Rust","code":"impl Solution {\n    pub fn count_submatrices(grid: Vec<Vec<i32>>, k: i32) -> i32 {\n        let n = grid.len();\n        let m = grid[0].len();\n        let mut ps = vec![vec![0; m+1]; n+1];\n        let mut ans = 0;\n        for i in 1..=n {\n            for j in 1..=m {\n                ps[i][j] = grid[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];\n                if ps[i][j] <= k {\n                    ans += 1;\n                }\n            }\n        }\n        ans\n    }\n}","lang":"rust"},{"language":"TypeScript","code":"class Solution {\n    countSubmatrices(grid: number[][], k: number): number {\n        const n = grid.length, m = grid[0].length;\n        const ps = Array.f

Related Tags