🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem requires us to find submatrices that:
- Include at least one 'X'.
- Have an equal number of 'X' and 'Y'.
- Start from the top-left corner of the matrix,
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.
Approach
- Prefix Difference Array:
- Use
prefix
array to storecount(X) - count(Y)
for each cell(i, j)
in the matrix. Initializeprefix[0][0] = 0
. - Populateprefix[i][j]
based on the values ofprefix[i-1][j]
,prefix[i][j-1]
, and adjust based ongrid[i][j]
being 'X' or 'Y'. - Tracking 'X' Occurrence:
- Use
hasX
array to record whether 'X' has appeared in any submatrix up to the current cell(i, j)
. - UpdatehasX[i][j]
based on whethergrid[i][j]
is 'X' or if 'X' has occurred in any preceding submatrix (hasX[i-1][j]
orhasX[i][j-1]
). - Counting Valid Submatrices:
- Iterate through all possible submatrices defined by top-left and bottom-right corners
(top, left)
and(bottom, right)
. - Calculate the sum ofprefix
values for the submatrix to check if it meets the conditions: - Contains at least one 'X' (prefix[bottom][right] > 0
). -prefix[bottom][right]
equalsprefix[top][left]
to ensure equal counts of 'X' and 'Y'. - CheckhasX[top][left]
to confirm 'X' has occurred in the submatrix.
Complexity
- Time Complexity:
O(n * m)
, wheren
is the number of rows andm
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. - Space Complexity:
O(n * m)
for storing the prefix arrayprefix
and the boolean matrixhasX
.
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.
Code
C++
class Solution {
public:
int numberOfSubmatrices(vector>& grid) {
int n = grid.size();
int m = grid[0].size();
int res = 0;
vector> prefix(n + 1, vector(m + 1, 0));
vector> hasX(n + 1, vector(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;
}
};
Python
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
Java
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;
}
}
JavaScript
/**
* @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;
};