Question

Approach

I store all buildings by row and by column and only need to know, for each row x, the smallest and largest column index y present and, for each column y, the smallest and largest row index x present. A building at (x,y) is covered iff there exists at least one building strictly above (some x' < x in same column), strictly below (x' > x in same column), strictly left (y' < y in same row) and strictly right (y' > y in same row). That is exactly the condition min_row_y < y < max_row_y and min_col_x < x < max_col_x. I precompute those mins/maxs for every row and column in O(m) time (m = number of buildings) and then count how many buildings satisfy both strict inequalities.

Implementation

class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        row_min = defaultdict(lambda: 10**9)
        row_max = defaultdict(lambda: -10**9)
        col_min = defaultdict(lambda: 10**9)
        col_max = defaultdict(lambda: -10**9)
        
        for x, y in buildings:
            if y < row_min[x]:
                row_min[x] = y
            if y > row_max[x]:
                row_max[x] = y
            if x < col_min[y]:
                col_min[y] = x
            if x > col_max[y]:
                col_max[y] = x
        
        cnt = 0
        for x, y in buildings:
            if row_min[x] < y < row_max[x] and col_min[y] < x < col_max[y]:
                cnt += 1
        return cnt

Complexities

• Time: O(m)
• Space: O(m)