#3531

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Covered Buildings

Determine how many buildings in an n x n city are completely surrounded using array scanning and hash lookup efficiently.

array hash table sorting

Problem Statement

You are given a city represented as an n x n grid and a list of unique building coordinates buildings[i] = [x, y]. A building is considered covered if there exists at least one building directly above, below, left, and right of it within the grid.

Return the total number of buildings that are covered on all four sides. Each building coordinate is unique and within the bounds 1 <= x, y <= n, and the goal is to efficiently identify fully surrounded buildings using array scanning and hash table lookups.

Examples

Example 1

Input: n = 3, buildings = [[1,2],[2,2],[3,2],[2,1],[2,3]]

Output: 1

Example 2

Input: n = 3, buildings = [[1,1],[1,2],[2,1],[2,2]]

Output: 0

Example 3

Input: n = 5, buildings = [[1,3],[3,2],[3,3],[3,5],[5,3]]

Output: 1

Constraints

2 <= n <= 105
1 <= buildings.length <= 105
buildings[i] = [x, y]
1 <= x, y <= n
All coordinates of buildings are unique.

Solution Approach

Map Coordinates by Axis

Group all buildings by their x and y coordinates in separate hash maps. This allows O(1) lookup for neighbors along the same row or column, directly supporting the array scanning plus hash lookup pattern.

Check Coverage per Building

Iterate through each building and for each, check if there is a neighbor to the left, right, above, and below using the grouped hash maps. Increment a counter only if all four directions have a neighbor.

Optimize with Sorting

Sort the lists of buildings along each axis to ensure that neighbor checks are efficient. This reduces unnecessary scans along rows or columns and aligns with the expected pattern for this problem.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Hash Table + Sorting

We can group the buildings by their x-coordinates and y-coordinates, storing them in hash tables $\text{g1}$ and $\text{g2}$, respectively. Here, $\text{g1[x]}$ represents all y-coordinates for buildings with x-coordinate $x$, and $\text{g2[y]}$ represents all x-coordinates for buildings with y-coordinate $y$. Then, we sort these lists.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

Continue Practicing

#3551 minimum swaps to sort by digit sum #3572 maximize ysum by picking a triplet of distinct xvalues #3606 coupon code validator