Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every candidate must contain (0, 0), so its top-left corner is fixed and only its bottom-right corner varies. Two prefix-count tables can tell us how many X and Y characters each such rectangle contains.

Approach

Scan the grid row by row. For each character type, compute its prefix count by adding the count above and to the left, subtracting their overlapping prefix, and adding one if the current cell matches that type. Treat missing boundary prefixes as zero.

Count the rectangle ending at the current cell when its X count is positive and equals its Y count. The positive check is essential: a rectangle containing only dots has equal counts but does not satisfy the requirement to contain an X. Each bottom-right corner identifies one rectangle, so every valid candidate is counted exactly once.

class Solution:
    def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
        n = len(grid)
        m = len(grid[0])
        res = 0
        x = [[0] * m for _ in range(n)]
        y = [[0] * m for _ in range(n)]

        for i in range(n):
            for j in range(m):
                x[i][j] = (
                    (x[i - 1][j] if i > 0 else 0)
                    + (x[i][j - 1] if j > 0 else 0)
                    - (x[i - 1][j - 1] if i > 0 and j > 0 else 0)
                    + (1 if grid[i][j] == 'X' else 0)
                )
                y[i][j] = (
                    (y[i - 1][j] if i > 0 else 0)
                    + (y[i][j - 1] if j > 0 else 0)
                    - (y[i - 1][j - 1] if i > 0 and j > 0 else 0)
                    + (1 if grid[i][j] == 'Y' else 0)
                )
                if x[i][j] and x[i][j] == y[i][j]:
                    res += 1

        return res

Complexity analysis

Let r and c be the character-grid dimensions. Time: O(r * c). Auxiliary space: O(r * c) for two prefix-count matrices.