Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A building is covered when another building exists on each side along both coordinate axes. The nearest neighbors are unnecessary: the minimum and maximum occupied coordinates on its row and column already tell us whether both directions are represented.

Approach

Scan the buildings and maintain the smallest and largest coordinate for each row, and the smallest and largest coordinate for each column. Then scan the buildings again. Count one only if its position lies strictly between both row extremes and strictly between both column extremes.

Strict comparisons are essential because a building cannot serve as its own covering neighbor. Being between the extremes guarantees a building on each corresponding side, even if there are empty cells in between. Separate maps store only occupied rows and columns, so the algorithm does not need to construct or scan the entire city grid.

class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        rows = defaultdict(lambda: [n, 0])
        cols = defaultdict(lambda: [n, 0])
        for c, r in buildings:
            rows[r][0] = min(rows[r][0], c)
            rows[r][1] = max(rows[r][1], c)
            cols[c][0] = min(cols[c][0], r)
            cols[c][1] = max(cols[c][1], r)

        res = 0
        for c, r in buildings:
            if rows[r][0] < c < rows[r][-1] and cols[c][0] < r < cols[c][-1]:
                res += 1

        return res

Complexity analysis

Let n = buildings.length. Time: O(n). Auxiliary space: O(n) for row/column extrema maps.