Count Top-Left-Anchored Submatrices Within a Sum Limit
Company: Natwest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Count Top-Left-Anchored Submatrices Within a Sum Limit
You are given an `m` by `n` integer matrix `grid` and an integer `k`.
Return the number of nonempty contiguous rectangular submatrices that contain cell `(0,0)` and whose element sum is less than or equal to `k`.
### Examples
**Example 1**
```text
Input: grid = [[2,1],[3,0]], k = 3
Output: 2
```
The qualifying submatrices are the single cell `[2]`, with sum two, and the top row `[2,1]`, with sum three. The other two rectangles containing `(0,0)` have sums five and six, so they do not qualify.
**Example 2**
```text
Input: grid = [[0,2,0],[1,0,1]], k = 3
Output: 5
```
The sums of rectangles from `(0,0)` through each possible bottom-right cell are:
```text
0 2 2
1 3 4
```
Five of these six rectangles have sum at most three. Distinct rectangles are counted separately even when they have equal sums.
### Constraints
- `m == grid.length`.
- `n == grid[i].length`.
- `1 <= m, n <= 1000`.
- `0 <= grid[i][j] <= 1000`.
- `1 <= k <= 10^9`.
### Clarifying Questions
- Must a counted rectangle begin at `(0,0)`? Yes; to contain row zero and column zero, its first row and first column must both be zero.
- Is equality with `k` accepted? Yes; the limit is inclusive.
- Do rectangles elsewhere in the matrix count? No, even if their sums are small enough.
- Are zeros allowed? Yes; equal sums do not make different rectangles the same rectangle.
- Can an empty rectangle be counted? No.
### C++ Interface
```cpp
class Solution {
public:
int countSubmatrices(vector<vector<int>>& grid, int k) {
}
};
```
### Reasoning Checkpoints
- Count exactly the nonempty rectangles containing `(0,0)` and apply the inclusive sum limit.
- Count distinct rectangles separately, including when zeros produce equal sums.
- Justify arithmetic and resource costs for the full matrix dimensions.
```hint Organize sums by the bottom-right cell
Every candidate begins at (0,0), so its bottom-right cell identifies it uniquely. While moving down the rows, consider cumulative column totals and a running sum across those columns.
```
Overview: Count contiguous submatrices containing the top-left cell whose sums are at most the given limit, including equality and zero-valued cells.
