3212. Count Submatrices With Equal Frequency of X and Y
Medium51.5% acceptance26,770 / 51,995 submissions
Asked by 1 company
Topics
Given a 2D character matrix grid, where grid[i][j] is either 'X', 'Y', or '.', return the number of submatrices that contain:
grid[0][0]- an equal frequency of
'X'and'Y'. - at least one
'X'.
Example 1:
Input: grid = [["X","Y","."],["Y",".","."]]
Output: 3
Explanation:
Example 2:
Input: grid = [["X","X"],["X","Y"]]
Output: 0
Explanation:
No submatrix has an equal frequency of 'X' and 'Y'.
Example 3:
Input: grid = [[".","."],[".","."]]
Output: 0
Explanation:
No submatrix has at least one 'X'.
Constraints:
1 <= grid.length, grid[i].length <= 1000grid[i][j]is either'X','Y', or'.'.
Hints
Hint 1
Replace
’X’ with 1, ’Y’ with -1 and ’.’ with 0.Hint 2
You need to find how many submatrices
grid[0..x][0..y] have a sum of 0 and at least one ’X’.Hint 3
Use prefix sum to calculate submatrices sum.