How do I efficiently solve the 'Number of Black Blocks' problem?

Use array scanning to iterate over all blocks and hash sets to optimize lookup of black cells within each block.

What data structure should I use to store black cell coordinates?

Use a hash set to store the coordinates of black cells, ensuring constant-time lookups when checking each block.

How do I handle large grids in the 'Number of Black Blocks' problem?

Focus only on blocks that contain black cells, reducing the number of blocks you need to check.

What is the time complexity of the optimal solution?

The time complexity is O(k + m*n), where k is the number of black cells and m*n is the number of blocks in the grid.

Can I modify the 'Number of Black Blocks' problem for non-square grids?

Yes, the approach can be adapted to handle grids with non-square dimensions by adjusting the block boundaries accordingly.

#2768

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

黑格子的数目

给你两个整数 m 和 n ，表示一个下标从 0 开始的 m x n 的网格图。给你一个下标从 0 开始的二维整数矩阵 coordinates ，其中 coordinates[i] = [x, y] 表示坐标为 [x, y] 的格子是黑色的，所有没出现在 coordinates 中的格子都是白…

数组哈希表枚举

题目描述

给你两个整数 m 和 n ，表示一个下标从 0 开始的 m x n 的网格图。

给你一个下标从 0 开始的二维整数矩阵 coordinates ，其中 coordinates[i] = [x, y] 表示坐标为 [x, y] 的格子是 黑色的 ，所有没出现在 coordinates 中的格子都是 白色的。

一个块定义为网格图中 2 x 2 的一个子矩阵。更正式的，对于左上角格子为 [x, y] 的块，其中 0 <= x < m - 1 且 0 <= y < n - 1 ，包含坐标为 [x, y] ，[x + 1, y] ，[x, y + 1] 和 [x + 1, y + 1] 的格子。

请你返回一个下标从 0 开始长度为 5 的整数数组 arr ，arr[i] 表示恰好包含 i 个黑色格子的块的数目。

示例 1：

输入：m = 3, n = 3, coordinates = [[0,0]]
输出：[3,1,0,0,0]
解释：网格图如下：

只有 1 个块有一个黑色格子，这个块是左上角为 [0,0] 的块。
其他 3 个左上角分别为 [0,1] ，[1,0] 和 [1,1] 的块都有 0 个黑格子。
所以我们返回 [3,1,0,0,0] 。

示例 2：

输入：m = 3, n = 3, coordinates = [[0,0],[1,1],[0,2]]
输出：[0,2,2,0,0]
解释：网格图如下：

有 2 个块有 2 个黑色格子（左上角格子分别为 [0,0] 和 [0,1]）。
左上角为 [1,0] 和 [1,1] 的两个块，都有 1 个黑格子。
所以我们返回 [0,2,2,0,0] 。

提示：

2 <= m <= 10⁵
2 <= n <= 10⁵
0 <= coordinates.length <= 10⁴
coordinates[i].length == 2
0 <= coordinates[i][0] < m
0 <= coordinates[i][1] < n
coordinates 中的坐标对两两互不相同。

lightbulb

解题思路

方法一：哈希表计数

对于每个 $2 \times 2$ 的子矩阵，我们可以用其左上角的坐标 $(x, y)$ 来表示它。

而对于每个黑格子 $(x, y)$ ，它对 $4$ 个子矩阵的贡献为 $1$ ，即矩阵 $(x - 1, y - 1)$ , $(x - 1, y)$ , $(x, y - 1)$ , $(x, y)$ 。

因此，我们遍历所有的黑格子，然后累计每个子矩阵中黑格子的个数，记录在哈希表 $cnt$ 中。

最后，我们遍历 $cnt$ 中的所有值（大于 $0$ ），统计其出现的次数，记录在答案数组 $ans$ 中，而 $ans[0]$ 则表示没有黑格子的子矩阵的个数，值为 $(m - 1) \times (n - 1) - \sum_{i = 1}^4 ans[i]$ 。

时间复杂度 $O(l)$ ，空间复杂度 $O(l)$ ，其中 $l$ 为 $coordinates$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def countBlackBlocks(
        self, m: int, n: int, coordinates: List[List[int]]
    ) -> List[int]:
        cnt = Counter()
        for x, y in coordinates:
            for a, b in pairwise((0, 0, -1, -1, 0)):
                i, j = x + a, y + b
                if 0 <= i < m - 1 and 0 <= j < n - 1:
                    cnt[(i, j)] += 1
        ans = [0] * 5
        for x in cnt.values():
            ans[x] += 1
        ans[0] = (m - 1) * (n - 1) - len(cnt.values())
        return ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates knowledge of hashing and efficient lookups.
question_mark
The candidate avoids checking unnecessary blocks in large grids.
question_mark
The candidate uses array scanning effectively, even for large inputs.

warning

常见陷阱

外企场景

error
Not utilizing a hash set to optimize lookups for black cell coordinates.
error
Iterating over every possible block without considering the sparsity of black cells.
error
Failing to handle edge cases where the number of blocks is large but the number of black cells is small.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider variations where black cells are clustered, affecting the distribution of black cells across blocks.
arrow_right_alt
Expand the problem to work with grids that may have a non-square shape.
arrow_right_alt
Modify the problem to count the number of white cells instead of black cells.

help

常见问题

外企场景

继续练习

#2605 从两个数字数组里生成最小数字 #2975 移除栅栏得到的正方形田地的最大面积 #3020 子集中元素的最大数量