Dare2Solve
The problem requires us to find submatrices that:
grid[0][0]
.To efficiently solve this, we'll use prefix arrays to maintain the cumulative difference between the counts of 'X' and 'Y' up to each point in the matrix. Additionally, we'll use a boolean matrix hasX
to keep track of whether 'X' has occurred in any preceding submatrix.
Prefix Difference Array:
prefix
array to store count(X) - count(Y)
for each cell (i, j)
in the matrix. Initialize prefix[0][0] = 0
.prefix[i][j]
based on the values of prefix[i-1][j]
, prefix[i][j-1]
, and adjust based on grid[i][j]
being 'X' or 'Y'.Tracking 'X' Occurrence:
hasX
array to record whether 'X' has appeared in any submatrix up to the current cell (i, j)
.hasX[i][j]
based on whether grid[i][j]
is 'X' or if 'X' has occurred in any preceding submatrix (hasX[i-1][j]
or hasX[i][j-1]
).Counting Valid Submatrices:
(top, left)
and (bottom, right)
.prefix
values for the submatrix to check if it meets the conditions:
prefix[bottom][right] > 0
).prefix[bottom][right]
equals prefix[top][left]
to ensure equal counts of 'X' and 'Y'.hasX[top][left]
to confirm 'X' has occurred in the submatrix.O(n * m)
, where n
is the number of rows and m
is the number of columns. This complexity arises due to the nested loops iterating over all submatrices and the adjustments made using prefix arrays and boolean flags.O(n * m)
for storing the prefix array prefix
and the boolean matrix hasX
.This approach ensures that we efficiently count the desired submatrices by leveraging prefix differences and boolean flags to track 'X' occurrences, ensuring that all conditions are checked optimally.
class Solution {
public:
int numberOfSubmatrices(vector<vector<char>>& grid) {
int n = grid.size();
int m = grid[0].size();
int res = 0;
vector<vector<int>> prefix(n + 1, vector<int>(m + 1, 0));
vector<vector<bool>> hasX(n + 1, vector<bool>(m + 1, false));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
prefix[i + 1][j + 1] = prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j];
hasX[i + 1][j + 1] = hasX[i + 1][j] || hasX[i][j + 1] || grid[i][j] == 'X';
if (grid[i][j] == 'X') prefix[i + 1][j + 1]++;
if (grid[i][j] == 'Y') prefix[i + 1][j + 1]--;
if (prefix[i + 1][j + 1] == 0 && hasX[i + 1][j + 1]) ++res;
}
}
return res;
}
};
class Solution:
def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
n = len(grid)
m = len(grid[0])
res = 0
prefix = [[0] * (m + 1) for _ in range(n + 1)]
hasX = [[False] * (m + 1) for _ in range(n + 1)]
for i in range(n):
for j in range(m):
prefix[i + 1][j + 1] = prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j]
hasX[i + 1][j + 1] = hasX[i + 1][j] or hasX[i][j + 1] or grid[i][j] == 'X'
if grid[i][j] == 'X':
prefix[i + 1][j + 1] += 1
if grid[i][j] == 'Y':
prefix[i + 1][j + 1] -= 1
if prefix[i + 1][j + 1] == 0 and hasX[i + 1][j + 1]:
res += 1
return res
class Solution {
public int numberOfSubmatrices(char[][] grid) {
int n = grid.length;
int m = grid[0].length;
int res = 0;
int[][] prefix = new int[n + 1][m + 1];
boolean[][] hasX = new boolean[n + 1][m + 1];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
prefix[i + 1][j + 1] = prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j];
hasX[i + 1][j + 1] = hasX[i + 1][j] || hasX[i][j + 1] || grid[i][j] == 'X';
if (grid[i][j] == 'X') prefix[i + 1][j + 1]++;
if (grid[i][j] == 'Y') prefix[i + 1][j + 1]--;
if (prefix[i + 1][j + 1] == 0 && hasX[i + 1][j + 1]) ++res;
}
}
return res;
}
}
/**
* @param {character[][]} grid
* @return {number}
*/
var numberOfSubmatrices = function (grid) {
var n = grid.length;
var m = grid[0].length;
var res = 0;
var prefix = Array.from({ length: n + 1 }, () => new Int32Array(m + 1));
var hasX = Array.from({ length: n + 1 }, () => new Uint8Array(m + 1));
for (var i = 0; i < n; ++i) {
for (var j = 0; j < m; ++j) {
prefix[i + 1][j + 1] = prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j];
hasX[i + 1][j + 1] = hasX[i + 1][j] || hasX[i][j + 1] || grid[i][j] === "X"
if (grid[i][j] === "X") prefix[i + 1][j + 1]++;
if (grid[i][j] === "Y") prefix[i + 1][j + 1]--;
if (prefix[i + 1][j + 1] === 0 && hasX[i + 1][j + 1]) ++res;
}
}
return res;
};