What is the main pattern used in Count Covered Buildings?

The main pattern is array scanning combined with hash lookups to check neighbors along rows and columns efficiently.

How do I handle edge buildings in the grid?

Edge buildings cannot be fully covered as one or more directions will lack neighbors, so they are automatically excluded from the count.

Can sorting improve performance in this problem?

Yes, sorting buildings within each axis group allows neighbor checks to stop early and reduces unnecessary scans, improving efficiency.

What is the time complexity for this approach?

Time complexity is O(b log b) due to sorting the buildings along each axis group, where b is the number of buildings.

Is GhostInterview suitable for practicing Count Covered Buildings?

Yes, GhostInterview specifically demonstrates the array scanning plus hash lookup pattern, helping implement the solution correctly and efficiently.

#3531

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

统计被覆盖的建筑

给你一个正整数 n ，表示一个 n x n 的城市，同时给定一个二维数组 buildings ，其中 buildings[i] = [x, y] 表示位于坐标 [x, y] 的一个唯一建筑。如果一个建筑在四个方向（左、右、上、下）中每个方向上都至少存在一个建筑，则称该建筑被覆盖。返回被…

数组哈希表排序

题目描述

给你一个正整数 n，表示一个 n x n 的城市，同时给定一个二维数组 buildings，其中 buildings[i] = [x, y] 表示位于坐标 [x, y] 的一个唯一建筑。

如果一个建筑在四个方向（左、右、上、下）中每个方向上都至少存在一个建筑，则称该建筑 被覆盖 。

返回 被覆盖 的建筑数量。

示例 1：

输入: n = 3, buildings = [[1,2],[2,2],[3,2],[2,1],[2,3]]

输出: 1

解释:

只有建筑 [2,2] 被覆盖，因为它在每个方向上都至少存在一个建筑：
- 上方 ([1,2])
- 下方 ([3,2])
- 左方 ([2,1])
- 右方 ([2,3])
因此，被覆盖的建筑数量是 1。

示例 2：

输入: n = 3, buildings = [[1,1],[1,2],[2,1],[2,2]]

输出: 0

解释:

没有任何一个建筑在每个方向上都有至少一个建筑。

示例 3：

输入: n = 5, buildings = [[1,3],[3,2],[3,3],[3,5],[5,3]]

输出: 1

解释:

只有建筑 [3,3] 被覆盖，因为它在每个方向上至少存在一个建筑：
- 上方 ([1,3])
- 下方 ([5,3])
- 左方 ([3,2])
- 右方 ([3,5])
因此，被覆盖的建筑数量是 1。

提示：

2 <= n <= 10⁵
1 <= buildings.length <= 10⁵
buildings[i] = [x, y]
1 <= x, y <= n
buildings 中所有坐标均唯一。

lightbulb

解题思路

方法一：哈希表 + 排序

我们可以将建筑按照横坐标和纵坐标进行分组，分别记录在哈希表 $\text{g1}$ 和 $\text{g2}$ 中，其中 $\text{g1[x]}$ 表示所有横坐标为 $x$ 的纵坐标，而 $\text{g2[y]}$ 表示所有纵坐标为 $y$ 的横坐标，然后我们将其进行排序。

接下来，我们遍历所有建筑，对于当前建筑 $(x, y)$ ，我们通过哈希表获取对应的纵坐标列表 $l_1$ 和横坐标列表 $l_2$ ，并检查条件以确定建筑是否被覆盖。覆盖的条件是 $l_2[0] < x < l_2[-1]$ 且 $l_1[0] < y < l_1[-1]$ ，若是，我们将答案加一。

遍历结束后，返回答案即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是建筑物的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        g1 = defaultdict(list)
        g2 = defaultdict(list)
        for x, y in buildings:
            g1[x].append(y)
            g2[y].append(x)
        for x in g1:
            g1[x].sort()
        for y in g2:
            g2[y].sort()
        ans = 0
        for x, y in buildings:
            l1 = g1[x]
            l2 = g2[y]
            if l2[0] < x < l2[-1] and l1[0] < y < l1[-1]:
                ans += 1
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on grouping and sorting: O(b log b) where b is the number of buildings, due to sorting each axis group. Space complexity is O(b) to store hash maps of coordinates for quick neighbor lookups.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect fast identification of fully surrounded buildings using combined array scanning and hash lookups.
question_mark
Look for efficient grouping by x and y coordinates to reduce neighbor checks.
question_mark
Sorting within axis groups can reveal optimization awareness and understanding of the coverage pattern.

warning

常见陷阱

外企场景

error
Forgetting to check all four directions and miscounting partially surrounded buildings.
error
Not grouping by axis, resulting in repeated scans and time limit issues.
error
Incorrectly handling edge buildings where one or more directions cannot have neighbors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count buildings with at least three neighbors instead of four.
arrow_right_alt
Identify uncovered buildings using the same hash lookup pattern.
arrow_right_alt
Extend to non-square grids or irregular coordinate bounds while maintaining the scanning approach.

help

常见问题

外企场景

继续练习

#3551 数位和排序需要的最小交换次数 #3572 选择不同 X 值三元组使 Y 值之和最大 #3606 优惠券校验器