Skip to content

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

Link

Solution⚓︎

2D Prefix Sum: Define prefix[i+1][j+1] to be the sum of elements of the submatrices with grid[0][0] in the upper left corner and grid[i][j] in the lower right corner. With this definition, there is no need to deal with the element sum of the first row/column.

See reference (Chinese).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int countSubmatrices(vector<vector<int>>& grid, int k) {
        int res = 0, m = grid.size(), n = grid[0].size();
        vector<vector<int>> prefix(m + 1, vector<int>(n + 1));

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i + 1][j + 1] = prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j] + grid[i][j];
                res += prefix[i + 1][j + 1] <= k;
            }
        }

        return res;
    }
};
  • Time complexity: \(O(mn)\);
  • Space complexity: \(O(mn)\).