3212. Count Submatrices With Equal Frequency of X and Y

Intuition

The problem requires us to find submatrices that:

1. Include at least one 'X'.
2. Have an equal number of 'X' and 'Y'.
3. 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

1. Prefix Difference Array: - Use prefix array to store count(X) - count(Y) for each cell (i, j) in the matrix. Initialize prefix[0][0] = 0. - Populate 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'.
2. Tracking 'X' Occurrence: - Use hasX array to record whether 'X' has appeared in any submatrix up to the current cell (i, j). - Update 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]).
3. Counting Valid Submatrices: - Iterate through all possible submatrices defined by top-left and bottom-right corners (top, left) and (bottom, right). - Calculate the sum of prefix values for the submatrix to check if it meets the conditions: - Contains at least one 'X' (prefix[bottom][right] > 0). - prefix[bottom][right] equals prefix[top][left] to ensure equal counts of 'X' and 'Y'. - Check hasX[top][left] to confirm 'X' has occurred in the submatrix.

Complexity

• Time Complexity: 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.
• Space Complexity: 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.

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;
};