[LeetCode] Find Sorted Submatrices With Maximum Element at Most K

3359. Find Sorted Submatrices With Maximum Element at Most K

You are given a 2D matrix grid of size m x n. You are also given a non-negative integer k.

Return the number of submatrices of grid that satisfy the following conditions:

  • The maximum element in the submatrix less than or equal to k.
  • Each row in the submatrix is sorted in non-increasing order.

A submatrix (x1, y1, x2, y2) is a matrix that forms by choosing all cells grid[x][y] where x1 <= x <= x2 and y1 <= y <= y2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
long long countSubmatrices(vector<vector<int>>& grid, int k) {
long long res = 0, n = grid.size(), m = grid[0].size();
grid.push_back(vector<int>(m,k + 1));
vector<vector<pair<long long, long long>>> dp(m);
auto clean = [&](int x) {
int t = 0;
for(int i = 0; i < dp[x].size(); i++) {
int h = dp[x].back().first - dp[x][i].first;
res += h * (h + 1) / 2 * (dp[x][i].second - t);
t = dp[x][i].second;
}
dp[x] = {};
};
for(int i = 0; i <= n; i++) {
for(long long j = 0, len = 0; j < m; j++) {
if(grid[i][j] > k) {
dp[j].push_back({i,0});
clean(j), len = 0;
} else {
if(!j or grid[i][j] <= grid[i][j-1]) len++;
else len = 1;
int pos = i;
while(dp[j].size() and dp[j].back().second > len) {
long long h = i - dp[j].back().first;
long long w = dp[j].back().second - max(len, dp[j].size() > 1 ? dp[j][dp[j].size()-2].second : 0);
res += h * (h + 1) / 2 * w;
pos = dp[j].back().first;
dp[j].pop_back();
}
if(dp[j].size() == 0 or dp[j].back().second != len) {
dp[j].push_back({pos,len});
}
}
}
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2024/11/24/PS/LeetCode/find-sorted-submatrices-with-maximum-element-at-most-k/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.