Repository navigation
Expand file tree
/
Copy pathCountSubmatricesWithEqualFrequencyX_Y.cpp
More file actions
71 lines (56 loc) · 1.81 KB
/
Copy pathCountSubmatricesWithEqualFrequencyX_Y.cpp
File metadata and controls
71 lines (56 loc) · 1.81 KB
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution
{
public:
int numberOfSubmatrices(vector<vector<char>>& grid)
{
int rows = grid.size();
int cols = grid[0].size();
// prefix count of X and Y
vector<vector<int>> prefixX(rows + 1, vector<int>(cols + 1, 0));
vector<vector<int>> prefixY(rows + 1, vector<int>(cols + 1, 0));
int validSubmatrices = 0;
for (int r = 1; r <= rows; r++)
{
for (int c = 1; c <= cols; c++)
{
// build prefix sums
prefixX[r][c] = prefixX[r - 1][c] + prefixX[r][c - 1] - prefixX[r - 1][c - 1];
prefixY[r][c] = prefixY[r - 1][c] + prefixY[r][c - 1] - prefixY[r - 1][c - 1];
// update based on current cell
if (grid[r - 1][c - 1] == 'X')
{
prefixX[r][c]++;
}
else if (grid[r - 1][c - 1] == 'Y')
{
prefixY[r][c]++;
}
// check condition
if (prefixX[r][c] > 0 && prefixX[r][c] == prefixY[r][c])
{
validSubmatrices++;
}
}
}
return validSubmatrices;
}
};
/*
APPROACH:
We use 2D prefix sum to count occurrences of 'X' and 'Y' in submatrices
from (0,0) to (r,c).
1. prefixX[r][c] → number of 'X' in rectangle (0,0) → (r-1,c-1)
2. prefixY[r][c] → number of 'Y' in rectangle (0,0) → (r-1,c-1)
At every cell (r,c):
- We build prefix sums using standard 2D prefix formula:
top + left - overlap
- Then we update based on current grid cell.
- If:
prefixX > 0 AND prefixX == prefixY
→ this submatrix (0,0 to r,c) is valid.
We count all such valid submatrices.
Time Complexity:
O(rows * cols)
Space Complexity:
O(rows * cols)
*/