How do I handle a grid with no 'X' or 'Y' characters?

In cases where there are no 'X' or 'Y', the result will always be 0 since there are no valid submatrices with equal frequencies of 'X' and 'Y'.

What is the purpose of transforming 'X' to 1, 'Y' to -1, and '.' to 0?

This transformation simplifies the problem by converting it to one of finding subarrays that sum to 0, which makes use of efficient techniques like prefix sums.

Can I use brute force to solve this problem?

While brute force is possible, it is inefficient, especially for large grids, and would lead to a time complexity of O(n^4) which is too slow.

How do I efficiently compute the sum of submatrices?

You can use a prefix sum array to compute the sum of any submatrix in constant time, reducing the time complexity significantly.

What if the matrix size increases to 1000x1000?

For large grids, it's essential to use optimized techniques like prefix sums and avoid brute-force enumeration of submatrices to ensure the solution remains efficient.

#3212

Medium

auto_awesome数组·matrix

LeetCode 题解工作台

统计 X 和 Y 频数相等的子矩阵数量

给你一个二维字符矩阵 grid ，其中 grid[i][j] 可能是 'X' 、 'Y' 或 '.' ，返回满足以下条件的子矩阵数量：包含 grid[0][0] 'X' 和 'Y' 的频数相等。至少包含一个 'X' 。示例 1：输入： grid = [["X","Y","."],["Y"…

数组矩阵前缀和

题目描述

给你一个二维字符矩阵 grid，其中 grid[i][j] 可能是 'X'、'Y' 或 '.'，返回满足以下条件的子矩阵数量：

包含 grid[0][0]
'X' 和 'Y' 的频数相等。
至少包含一个 'X'。

示例 1：

输入： grid = [["X","Y","."],["Y",".","."]]

输出： 3

解释：

示例 2：

输入： grid = [["X","X"],["X","Y"]]

输出： 0

解释：

不存在满足 'X' 和 'Y' 频数相等的子矩阵。

示例 3：

输入： grid = [[".","."],[".","."]]

输出： 0

解释：

不存在满足至少包含一个 'X' 的子矩阵。

提示：

1 <= grid.length, grid[i].length <= 1000
grid[i][j] 可能是 'X'、'Y' 或 '.'.

lightbulb

解题思路

方法一：二维前缀和

根据题目描述，我们只需要统计每个位置 $(i, j)$ 的前缀和 $s[i][j][0]$ 和 $s[i][j][1]$ ，分别表示从 $(0, 0)$ 到 $(i, j)$ 的子矩阵中字符 X 和 Y 的数量，如果 $s[i][j][0] > 0$ 且 $s[i][j][0] = s[i][j][1]$ ，则说明满足题目条件，答案加一。

遍历完所有位置后，返回答案即可。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别表示矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        s = [[[0] * 2 for _ in range(n + 1)] for _ in range(m + 1)]
        ans = 0
        for i, row in enumerate(grid, 1):
            for j, x in enumerate(row, 1):
                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]
                if x != ".":
                    s[i][j][ord(x) & 1] += 1
                if s[i][j][0] > 0 and s[i][j][0] == s[i][j][1]:
                    ans += 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check for a transformation approach involving numerical mapping of 'X', 'Y', and '.' to facilitate zero-sum subarray counting.
question_mark
Look for efficient usage of prefix sums to avoid brute-force submatrix enumeration.
question_mark
Ensure that the candidate identifies and handles edge cases such as grids with only '.' or one type of character.

warning

常见陷阱

外企场景

error
Using brute force to check every possible submatrix will result in a time complexity that is too high for larger grids.
error
Forgetting to transform the grid correctly, which can lead to incorrect results when checking submatrices.
error
Not properly handling edge cases such as grids with no 'X' or 'Y' characters, which can cause miscounts.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the grid size is fixed, say 10x10? Can you optimize for this case?
arrow_right_alt
What happens if the grid contains additional characters, such as 'A' or 'Z'? How would you adjust the approach?
arrow_right_alt
How would you adapt the solution if instead of equal counts of 'X' and 'Y', you needed a specific ratio of 'X' to 'Y'?

help

常见问题

外企场景

继续练习

#3225 网格图操作后的最大分数 #3070 元素和小于等于 k 的子矩阵的数目 #2906 构造乘积矩阵