Problem Description

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

• The element grid[0][0].
• An equal frequency of 'X' and 'Y'.
• At least one 'X'.

Intuition

To solve this problem, the goal is to find submatrices fulfilling specific conditions efficiently. We employ a 2D prefix sum approach which helps calculate the cumulative frequency of characters 'X' and 'Y' up to any given cell (i, j).

• Prefix Sum Array: We create a 3D prefix sum array s where s[i][j][0] tracks the number of 'X's and s[i][j][1] tracks the number of 'Y's from (0, 0) to (i, j).
• Calculation: As we iterate through the matrix:
  • Update the prefix sum at(i, j) using:
    • s[i][j][0] = s[i-1][j][0] + s[i][j-1][0] - s[i-1][j-1][0] and similarly for s[i][j][1].
  • Increment s[i][j][ord(x) & 1] if the current cell is not '.' (ord('X') & 1 == 0, ord('Y') & 1 == 1).
• Checking Condition: For each cell (i, j), check:
  • If s[i][j][0] is greater than zero.
  • If the number of 'X's is equal to 'Y's.
  • If both conditions are satisfied, count this submatrix as valid.

This method is efficient because it allows us to check conditions over a grid submatrix using calculated prefix sums, reducing the need for multiple nested loops.

Learn more about Prefix Sum patterns.

Solution Approach

2D Prefix Sum

In this problem, the main challenge is efficiently counting the number of submatrices that meet the criteria. We make use of a 2D prefix sum array to handle this:

1. Initialize Prefix Sum Array: We create a 3D array s where s[i][j][0] keeps track of the number of 'X's, and s[i][j][1] tracks the number of 'Y's in the submatrix from (0, 0) to (i, j).

2. Iterate Over the Grid: As we traverse each cell (i, j) in the grid:

   • Update the prefix sums using:
     • s[i][j][0] = s[i-1][j][0] + s[i][j-1][0] - s[i-1][j-1][0]
     • s[i][j][1] = s[i-1][j][1] + s[i][j-1][1] - s[i-1][j-1][1]
   • If the current cell (i, j) contains either 'X' or 'Y', increase the appropriate count:
     • s[i][j][ord(grid[i-1][j-1]) & 1] += 1 because the characters are offset by 1.

3. Check Conditions: For each position (i, j), determine if it forms a valid submatrix by checking:

   • s[i][j][0] > 0, ensuring at least one 'X' is present.
   • s[i][j][0] == s[i][j][1], assuring equal counts of 'X's and 'Y's.

4. Counting Valid Submatrices: If the conditions hold true, increment the answer by one.

This step-by-step method allows us to efficiently sum up the valid submatrices using prefix sums, reducing computational complexity by avoiding repetitive recalculations.

Example Walkthrough

Let's walk through an example to illustrate the solution approach. Consider the following grid:

grid = [
  ['X', '.', 'Y'],
  ['Y', 'X', '.'],
  ['.', 'Y', 'X']
]

We aim to find all the submatrices starting from grid[0][0], where the frequencies of 'X's and 'Y's are equal, with at least one 'X'.

Step 1: Initialize Prefix Sum Array

We start by creating a prefix sum array s with dimensions [rows+1][cols+1][2], initialized to zero. This will store the counts of 'X's (index 0) and 'Y's (index 1) for each submatrix (0,0) to (i,j).

Step 2: Fill the Prefix Sum Array

Iterate over each cell (i, j) in grid, updating the prefix sum:

• For cell (1, 1):
  • Contains 'X': s[1][1][0] = s[0][1][0] + s[1][0][0] - s[0][0][0] + 1 = 1
  • s[1][1][1] = s[0][1][1] + s[1][0][1] - s[0][0][1] = 0

Continue this process for the entire grid.

Step 3: Check Conditions for Valid Submatrices

For each position (i, j), check if the submatrix satisfies the conditions:

• (i, j) = (1, 1):
  • s[1][1][0] > 0 ensures at least one 'X'.
  • s[1][1][0] == s[1][1][1] checks equal 'X' and 'Y'.

Proceed with checking submatrices starting from grid[0][0] by comparing the prefix sums.

Step 4: Count Valid Submatrices

The above conditions help identify valid submatrices. In our example grid, the following submatrices satisfy all conditions:

• Submatrix [(0,0) to (1,2)]: Contains 2 'X's and 2 'Y's.

Through efficient prefix sum calculations, count these submatrices and return the total number.

This method capitalizes on the prefix sum strategy to minimize redundant calculations, ensuring a more efficient solution.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(m \times n) because it involves iterating over each element of the m x n grid to compute prefix sums and check conditions, where m is the number of rows and n is the number of columns.

The space complexity of the code is O(m \times n) due to the usage of the 3D list s, which stores additional data for every element of the m x n grid.

Learn more about how to find time and space complexity quickly.