Show problems as
Classic problem #3212MediumArrayMatrixPrefix Sum

Count Submatrices With Equal Frequency of X and Y

Real-world version: Corner Blocks With Matching Marks
Tracked in this browser only
Read Count Submatrices With Equal Frequency of X and Y on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A board is given as grid, each cell holding 'X', 'Y' or '.'.

A corner block is a rectangle of cells whose top-left cell is the board's own top-left cell. A corner block balances when it holds as many 'X' marks as 'Y' marks and holds at least one 'X'.

Return how many corner blocks balance.

Examples

Example 1

Input
grid = [["X", ".", "Y", "X"], [".", "Y", "X", "."], ["Y", "X", ".", "Y"]]
Output
7

Each corner block is named by its bottom-right cell. Those whose X and Y counts come out level, with at least one X present, are the ones counted.

Example 2

Input
grid = [["X", "Y"]]
Output
1

The block ending at the first cell holds one X and no Y, so it does not balance. The block covering both cells holds one of each, so it does.

Example 3

Input
grid = [["."]]
Output
0

The only block holds no X at all, so nothing balances.

Constraints

  • 1 <= grid.length <= 1000
  • 1 <= grid[i].length <= 1000
  • Every row of grid has the same length
  • grid[i][j] is 'X', 'Y' or '.'

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def number_of_submatrices(grid: list[list[str]]) -> int:
Java
public int numberOfSubmatrices(char[][] grid)

More on the same topics