3212. Count Submatrices With Equal Frequency of X and Y

Description

Given a 2D character matrix grid, where grid[i][j] is either 'X', 'Y', or '.', return the number of that contain:

• grid[0][0]
• an equal frequency of 'X' and 'Y'.
• at least one 'X'.

 

Example 1:

Input: grid = [["X","Y","."],["Y",".","."]]

Output: 3

Explanation:

Example 2:

Input: grid = [["X","X"],["X","Y"]]

Output: 0

Explanation:

No submatrix has an equal frequency of 'X' and 'Y'.

Example 3:

Input: grid = [[".","."],[".","."]]

Output: 0

Explanation:

No submatrix has at least one 'X'.

 

Constraints:

• 1 <= grid.length, grid[i].length <= 1000
• grid[i][j] is either 'X', 'Y', or '.'.

 

Solutions

Solution: Prefix Sum

• Time complexity: O(mn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {character[][]} grid
 * @return {number}
 */
const numberOfSubmatrices = function (grid) {
  const m = grid.length;
  const n = grid[0].length;
  let prevRowX = Array.from({ length: n }, () => 0);
  let prevRowY = Array.from({ length: n }, () => 0);
  let result = 0;

  for (let row = 0; row < m; row++) {
    const currentRowX = new Array(n).fill(0);
    const currentRowY = new Array(n).fill(0);

    for (let col = 0; col < n; col++) {
      const value = grid[row][col];
      const topX = prevRowX[col];
      const leftX = currentRowX[col - 1] ?? 0;
      const cornerX = prevRowX[col - 1] ?? 0;
      const topY = prevRowY[col];
      const leftY = currentRowY[col - 1] ?? 0;
      const cornerY = prevRowY[col - 1] ?? 0;

      currentRowX[col] = topX + leftX - cornerX + (value === 'X' ? 1 : 0);
      currentRowY[col] = topY + leftY - cornerY + (value === 'Y' ? 1 : 0);

      if (currentRowX[col] && currentRowX[col] === currentRowY[col]) {
        result += 1;
      }
    }

    prevRowX = currentRowX;
    prevRowY = currentRowY;
  }

  return result;
};