# Count Submatrices with Top-Left Element and Sum Less Than k
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-submatrices-with-top-left-element-and-sum-less-than-k)
Canonical: https://scaleengineer.com/dsa/problems/count-submatrices-with-top-left-element-and-sum-less-than-k
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Matrix
**Companies:** [Barclays](https://scaleengineer.com/companies/barclays)
---
## Problem
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.glich.co/dsa/count-submatrices-with-top-left-element-and-sum-less-than-k/image0.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.glich.co/dsa/count-submatrices-with-top-left-element-and-sum-less-than-k/image1.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`

# Approaches
## Brute Force Iteration
The most straightforward approach is to iterate through every possible submatrix that starts at the top-left corner `(0, 0)`. A submatrix is defined by its bottom-right corner `(r, c)`. We can iterate through all possible `r` and `c`, and for each, we calculate the sum of the corresponding submatrix by iterating through all its elements. If the sum is less than or equal to `k`, we increment a counter.
**Time:** O(m^2 * n^2), where `m` is the number of rows and `n` is the number of columns. For each of the `m*n` possible bottom-right corners, we iterate up to `m*n` elements to calculate the sum. · **Space:** O(1), as we only use a few variables to store the count and the current sum, not dependent on the input size.
**Pros:** Simple to understand and implement.; Uses minimal extra space.
**Cons:** Highly inefficient due to nested loops.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
This method uses a brute-force strategy. It considers every possible bottom-right corner `(r, c)` for a submatrix that must include the top-left element `(0, 0)`. For each of these `m * n` potential submatrices, it calculates the sum by iterating over all the cells within that submatrix's bounds. This leads to recalculating sums of smaller submatrices multiple times.

For example, when calculating the sum for the submatrix ending at `(r, c)`, we re-sum all the elements that were already part of the submatrix ending at `(r, c-1)`.

```java
class Solution {
    public int countSubmatrices(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;

        // Iterate through all possible bottom-right corners (r, c)
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                // Calculate the sum of the submatrix from (0,0) to (r,c)
                long currentSum = 0;
                for (int i = 0; i <= r; i++) {
                    for (int j = 0; j <= c; j++) {
                        currentSum += grid[i][j];
                    }
                }

                // Check if the sum is within the limit
                if (currentSum <= k) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Iterate through each possible row `r` from `0` to `m-1` (where `m` is the number of rows).
- Inside this loop, iterate through each possible column `c` from `0` to `n-1` (where `n` is the number of columns).
- Each pair `(r, c)` defines the bottom-right corner of a submatrix starting at `(0, 0)`.
- For each submatrix, calculate its sum by iterating from row `i = 0` to `r` and column `j = 0` to `c` and adding `grid[i][j]` to a `currentSum`.
- If `currentSum` is less than or equal to `k`, increment `count`.
- After all loops complete, return `count`.

## 2D Prefix Sum with Auxiliary Matrix
To avoid the redundant calculations of the brute-force approach, we can use a technique called 2D prefix sums. We precompute the sums of all submatrices starting at `(0, 0)` and store them in an auxiliary matrix. The sum of a submatrix with its bottom-right corner at `(r, c)` can then be retrieved in `O(1)` time.
**Time:** O(m * n). Building the prefix sum matrix takes O(m * n), and iterating through it to count valid submatrices also takes O(m * n). The total complexity is linear with respect to the number of cells in the grid. · **Space:** O(m * n) to store the auxiliary `prefixSum` matrix.
**Pros:** Efficient time complexity, suitable for the given constraints.; Conceptually clean separation of precomputation and counting.
**Cons:** Requires extra space proportional to the size of the input grid.
### Explanation
This approach significantly improves performance by building a 2D prefix sum matrix. Let's call it `prefixSum`. The cell `prefixSum[i][j]` will store the sum of all elements in the rectangle from `(0, 0)` to `(i-1, j-1)` in the original grid. This matrix can be built in a single pass over the grid.

Once the `prefixSum` matrix is constructed, we can simply iterate through it. Each entry `prefixSum[r+1][c+1]` directly gives us the sum of the submatrix we are interested in (the one with bottom-right corner `(r, c)`). We check if this sum is less than or equal to `k` and update our count accordingly.

```java
class Solution {
    public int countSubmatrices(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        
        // prefixSum[i][j] stores the sum of submatrix from (0,0) to (i-1, j-1)
        int[][] prefixSum = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefixSum[i][j] = grid[i - 1][j - 1] 
                                + prefixSum[i - 1][j] 
                                + prefixSum[i][j - 1] 
                                - prefixSum[i - 1][j - 1];
            }
        }

        int count = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (prefixSum[i][j] <= k) {
                    count++;
                }
            }
        }
        
        return count;
    }
}
```
### Algorithm
- Create an auxiliary 2D array `prefixSum` of size `(m+1) x (n+1)`.
- Populate the `prefixSum` matrix. For each cell `(i, j)` in the original grid, `prefixSum[i+1][j+1]` is calculated using the formula: `prefixSum[i+1][j+1] = grid[i][j] + prefixSum[i][j+1] + prefixSum[i+1][j] - prefixSum[i][j]`.
- Initialize a counter `count` to 0.
- Iterate through the `prefixSum` matrix from `(1, 1)` to `(m, n)`.
- For each cell `(i, j)`, the value `prefixSum[i][j]` represents the sum of the submatrix from `(0,0)` to `(i-1, j-1)`.
- If `prefixSum[i][j] <= k`, increment `count`.
- Return `count`.

## Optimized 2D Prefix Sum (In-place)
This approach is a space-optimized version of the 2D Prefix Sum method. Instead of creating a new matrix to store prefix sums, we can modify the input `grid` in-place. The cell `grid[i][j]` is updated to hold the sum of the submatrix from `(0, 0)` to `(i, j)`. This achieves the same time efficiency as the previous approach but with constant extra space.
**Time:** O(m * n). We iterate through each cell of the grid exactly once, performing constant time operations for each cell. · **Space:** O(1), as no additional data structures proportional to the input size are used. This assumes that modifying the input grid is acceptable.
**Pros:** Optimal time complexity of O(m * n).; Optimal space complexity of O(1) (if input modification is allowed).
**Cons:** Modifies the original input grid, which might be an undesirable side effect in some contexts.
### Explanation
We can achieve optimal space complexity by recognizing that the prefix sum for `grid[i][j]` only depends on the values in the row above and the column to the left, which have already been converted to prefix sums in our traversal order. Therefore, we can overwrite the input `grid` with its prefix sums.

We iterate through each cell of the grid. For each cell `(i, j)`, we calculate its prefix sum using the already computed prefix sums of its neighbors: `grid[i-1][j]`, `grid[i][j-1]`, and `grid[i-1][j-1]`. Immediately after computing the prefix sum for `(i, j)`, we check if it's less than or equal to `k` and update our count. This combines the computation and counting steps into a single pass.

```java
class Solution {
    public int countSubmatrices(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // Calculate prefix sum for grid[i][j] in-place
                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];
                }

                // Check if the sum is within the limit
                if (grid[i][j] <= k) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize `count` to 0.
- Iterate through the grid with row `i` from `0` to `m-1` and column `j` from `0` to `n-1`.
- In each iteration, update `grid[i][j]` to store the prefix sum of the submatrix ending at `(i, j)`.
- The update rule is: `grid[i][j] += grid[i-1][j]` (if `i>0`), `grid[i][j] += grid[i][j-1]` (if `j>0`), and `grid[i][j] -= grid[i-1][j-1]` (if `i>0` and `j>0`).
- After updating `grid[i][j]`, check if its new value is less than or equal to `k`.
- If `grid[i][j] <= k`, increment `count`.
- After the loops finish, return `count`.

# Solutions
### Java

```java
class Solution {
public
  int countSubmatrices(int[][] grid, int k) {
    int m = grid.length, n = grid[0].length;
    int[][] s = new int[m + 1][n + 1];
    int ans = 0;
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        s[i][j] =
            s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + grid[i - 1][j - 1];
        if (s[i][j] <= k) {
          ++ans;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countSubmatrices(vector<vector<int>> &grid, int k) {
    int m = grid.size(), n = grid[0].size();
    int s[m + 1][n + 1];
    memset(s, 0, sizeof(s));
    int ans = 0;
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        s[i][j] =
            s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + grid[i - 1][j - 1];
        if (s[i][j] <= k) {
          ++ans;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countSubmatrices(self, grid: List[List[int]], k: int) -> int: s = [[0] * (len(grid[0]) + 1) for _ in range(len(grid) + 1)] ans = 0 for i, row in enumerate(grid, 1): for j, x in enumerate(row, 1): s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x ans += s[i][j] <= k return ans

```