Balanced X and Y From the Corner

Medium

You are given a board board where every cell is 'X', 'Y' or '.'. Consider the rectangles that start at the top-left cell (0, 0) and end at any cell (i, j). Count how many of these rectangles satisfy both: - they contain as many 'X' cells as 'Y' cells; - they contain at least one 'X'.

Example 1

board=[['X', 'Y', '.'], ['Y', '.', '.']] → 3

The rectangles ending at (0, 1), (0, 2) and (1, 0) qualify, each with one X and one Y. The rest have an unmatched X or an extra Y.

Example 2

board=[['.', 'Y'], ['.', 'X']] → 1

Only the whole board has equal counts (one of each) and at least one X.

Example 3

board=[['Y', 'X']] → 1

Constraints

1 ≤ rows, columns ≤ 1000
board[i][j] is 'X', 'Y' or '.'

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Matrix Prefix Sum

Similar problems

Largest Light Square Medium Neighbourhood Sums in a Grid Medium K-th Largest Corner XOR Medium Three Heaviest Diamonds Medium Balanced Square in a Grid Medium

Input

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

Expected

Run checks the first 3 tests in your browser. Submit checks all 48 tests on the server, hidden ones included.