Problem Description

You are given a 2D character matrix grid where each cell grid[i][j] contains one of three possible values: 'X', 'Y', or '.'.

Your task is to count how many submatrices satisfy ALL of the following conditions:

1. The submatrix must include the top-left corner of the grid (position grid[0][0])
2. The submatrix must contain an equal number of 'X' and 'Y' characters
3. The submatrix must contain at least one 'X' character

A submatrix is defined by its top-left corner at (0, 0) and any bottom-right corner at position (i, j) where 0 ≤ i < m and 0 ≤ j < n (where m and n are the dimensions of the grid).

For example, if you have a 3×3 grid, possible submatrices that start at (0, 0) could end at positions like (0, 0), (0, 1), (1, 1), (2, 2), etc. Each such submatrix is checked to see if it meets the three conditions above.

The dot character '.' is neutral and doesn't count as either 'X' or 'Y'.

Return the total number of submatrices that satisfy all the conditions.

Intuition

Since we need to check all submatrices that start at position (0, 0), we essentially need to examine every possible bottom-right corner position (i, j) in the grid. For each such position, we need to quickly determine:

• How many 'X' characters are in the submatrix from (0, 0) to (i, j)
• How many 'Y' characters are in the submatrix from (0, 0) to (i, j)

If we calculate this naively for each position, we'd have to traverse the entire submatrix every time, which would be inefficient.

The key insight is to use 2D prefix sums. This technique allows us to precompute cumulative counts as we traverse the grid, so we can instantly know the count of 'X' and 'Y' characters in any submatrix starting from (0, 0).

For each position (i, j), we can calculate the prefix sum using the formula:

• s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + current_cell_value

The subtraction of s[i-1][j-1] is necessary because when we add s[i-1][j] and s[i][j-1], we're counting the rectangle from (0, 0) to (i-1, j-1) twice.

We maintain two separate prefix sums: one for counting 'X' characters and another for counting 'Y' characters. As we build these prefix sums for each position, we can immediately check if:

1. The count of 'X' is greater than 0 (at least one 'X' exists)
2. The count of 'X' equals the count of 'Y' (equal frequency)

If both conditions are met, we've found a valid submatrix and increment our answer.

This approach is efficient because we only traverse the grid once, and at each position, we can determine in constant time whether the submatrix from (0, 0) to that position is valid.

Learn more about Prefix Sum patterns.

Solution Approach

We implement the solution using a 2D prefix sum approach. Here's how the algorithm works:

Data Structure Setup: We create a 3D array s with dimensions (m+1) × (n+1) × 2, where:

• s[i][j][0] stores the count of 'X' characters in the submatrix from (0, 0) to (i-1, j-1)
• s[i][j][1] stores the count of 'Y' characters in the submatrix from (0, 0) to (i-1, j-1)
• We use 1-indexed arrays (hence m+1 and n+1) to avoid boundary checks

Algorithm Steps:

1. Initialize the prefix sum array with zeros and set answer counter ans = 0

2. Traverse the grid row by row, and for each cell at position (i, j):

   a. Calculate prefix sums using the inclusion-exclusion principle:

   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]

   b. Update counts based on the current cell:

   • If the cell contains 'X' or 'Y', increment the corresponding counter
   • The clever part: ord(x) & 1 gives us 0 for 'X' (ASCII 88) and 1 for 'Y' (ASCII 89)
   • If the cell is '.', we skip updating (it doesn't contribute to either count)

   c. Check validity of the submatrix from (0, 0) to current position:

   • If s[i][j][0] > 0 (at least one 'X' exists) AND
   • If s[i][j][0] == s[i][j][1] (equal frequency of 'X' and 'Y')
   • Then increment the answer counter

3. Return the final count of valid submatrices

Time Complexity: O(m × n) where m and n are the dimensions of the grid, as we visit each cell exactly once.

Space Complexity: O(m × n) for storing the prefix sum array.

The beauty of this solution is that it computes everything in a single pass through the grid, making it highly efficient compared to checking every possible submatrix individually.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 3×3 grid:

X Y .
Y X Y
. Y X

We'll build our prefix sum array s with dimensions 4×4×2 (using 1-indexing). Initially, all values are 0.

Step-by-step traversal:

Position (0,0) - Character 'X':

• Calculate prefix sums: s[1][1][0] = 0 + 0 - 0 = 0, s[1][1][1] = 0 + 0 - 0 = 0
• Current cell is 'X', so increment s[1][1][0] by 1 → s[1][1][0] = 1
• Check validity: s[1][1][0] = 1 > 0 ✓ and s[1][1][0] = 1 ≠ s[1][1][1] = 0 ✗
• No valid submatrix yet

Position (0,1) - Character 'Y':

• Calculate prefix sums: s[1][2][0] = 0 + 1 - 0 = 1, s[1][2][1] = 0 + 0 - 0 = 0
• Current cell is 'Y', so increment s[1][2][1] by 1 → s[1][2][1] = 1
• Check validity: s[1][2][0] = 1 > 0 ✓ and s[1][2][0] = 1 == s[1][2][1] = 1 ✓
• Found valid submatrix! ans = 1

Position (0,2) - Character '.':

• Calculate prefix sums: s[1][3][0] = 0 + 1 - 0 = 1, s[1][3][1] = 0 + 1 - 0 = 1
• Current cell is '.', so no increment
• Check validity: s[1][3][0] = 1 > 0 ✓ and s[1][3][0] = 1 == s[1][3][1] = 1 ✓
• Found valid submatrix! ans = 2

Position (1,0) - Character 'Y':

• Calculate prefix sums: s[2][1][0] = 1 + 0 - 0 = 1, s[2][1][1] = 0 + 0 - 0 = 0
• Current cell is 'Y', so increment s[2][1][1] by 1 → s[2][1][1] = 1
• Check validity: s[2][1][0] = 1 > 0 ✓ and s[2][1][0] = 1 == s[2][1][1] = 1 ✓
• Found valid submatrix! ans = 3

Position (1,1) - Character 'X':

• Calculate prefix sums: s[2][2][0] = 1 + 1 - 0 = 2, s[2][2][1] = 1 + 1 - 0 = 2
• Current cell is 'X', so increment s[2][2][0] by 1 → s[2][2][0] = 3
• Check validity: s[2][2][0] = 3 > 0 ✓ and s[2][2][0] = 3 ≠ s[2][2][1] = 2 ✗
• No valid submatrix

Position (1,2) - Character 'Y':

• Calculate prefix sums: s[2][3][0] = 1 + 3 - 1 = 3, s[2][3][1] = 1 + 2 - 1 = 2
• Current cell is 'Y', so increment s[2][3][1] by 1 → s[2][3][1] = 3
• Check validity: s[2][3][0] = 3 > 0 ✓ and s[2][3][0] = 3 == s[2][3][1] = 3 ✓
• Found valid submatrix! ans = 4

Continuing this process for the remaining positions (2,0), (2,1), and (2,2), we find that:

• Position (2,0): Not valid (3 X's, 2 Y's)
• Position (2,1): Not valid (4 X's, 3 Y's)
• Position (2,2): Valid (4 X's, 4 Y's) → ans = 5

Final answer: 5 valid submatrices

The valid submatrices are those ending at positions: (0,1), (0,2), (1,0), (1,2), and (2,2).

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm uses nested loops to iterate through the grid. The outer loop runs m times (for each row), and the inner loop runs n times (for each column). Within the nested loops, all operations are constant time O(1):

• Array access and assignment operations for the prefix sum array s
• Arithmetic operations (addition and subtraction)
• Character comparison and bitwise operation ord(x) & 1
• Conditional checks

Therefore, the overall time complexity is O(m × n).

Space Complexity: O(m × n)

The algorithm creates a 3D array s with dimensions (m + 1) × (n + 1) × 2. This array stores the prefix sums for tracking two different types of elements (determined by ord(x) & 1). The total number of elements in this array is (m + 1) × (n + 1) × 2, which is O(m × n) in terms of space complexity.

The remaining variables (m, n, ans, i, j, x) use constant space O(1).

Therefore, the overall space complexity is O(m × n).

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

Common Pitfalls

1. Incorrect Character Type Mapping

The code uses ord(cell_value) & 1 to determine character type, which maps 'X' to 0 and 'Y' to 1. However, the problem description and comments suggest checking for 'X' characters specifically (condition: "at least one 'X' character"). This creates confusion about which index represents which character.

The Issue:

• 'X' (ASCII 88) & 1 = 0, so 'X' counts are stored at index 0
• 'Y' (ASCII 89) & 1 = 1, so 'Y' counts are stored at index 1
• But the validity check uses prefix_sum[row_idx][col_idx][0] > 0 to verify "at least one 'X'"

Solution: Make the mapping explicit and consistent:

# Clear mapping
if cell_value == 'X':
    prefix_sum[row_idx][col_idx][0] += 1
elif cell_value == 'Y':
    prefix_sum[row_idx][col_idx][1] += 1

# Then check: at least one 'X' AND equal counts
if (prefix_sum[row_idx][col_idx][0] > 0 and 
    prefix_sum[row_idx][col_idx][0] == prefix_sum[row_idx][col_idx][1]):
    result_count += 1

2. Forgetting the Top-Left Corner Requirement

The current implementation correctly handles this by always computing submatrices from (0,0), but developers might mistakenly try to optimize by checking all possible submatrices, not just those starting at the top-left corner.

Wrong Approach:

# DON'T do this - checks ALL submatrices
for start_row in range(rows):
    for start_col in range(cols):
        for end_row in range(start_row, rows):
            for end_col in range(start_col, cols):
                # Check submatrix...

Correct Approach: Always start from (0,0) as the code currently does.

3. Off-by-One Errors with 1-Indexed Arrays

Using 1-indexed arrays for prefix sums can lead to indexing mistakes when accessing the original grid.

Potential Bug:

# Wrong: using row_idx/col_idx directly on grid
if grid[row_idx][col_idx] != ".":  # IndexError!

Correct Usage:

# Use enumerate with start=1 and access via loop variable
for row_idx, row_data in enumerate(grid, 1):
    for col_idx, cell_value in enumerate(row_data, 1):
        # cell_value is already the correct value from grid

4. Misunderstanding Empty Cells

Developers might incorrectly handle '.' characters by either counting them or excluding submatrices containing them entirely.

Wrong Interpretation:

# DON'T skip submatrices with dots
if has_dot_in_submatrix:
    continue  # Wrong! Dots are neutral

Correct Handling: Dots should be ignored in counting but not prevent a submatrix from being valid. The current code handles this correctly by simply not incrementing any counter when encountering '.'.