Problem Statement in English

You are given a 2D integer array buildings where buildings[i] = [x_i, y_i] represents a building located at coordinates (x_i, y_i) on a 2D plane.

A building (x, y) is covered if there are buildings located in all $4$ directions.

Return the number of covered buildings.

Approach

Honestly, this problem is mostly about observation. The first thing that you need to realize is that a building is covered if and only if there exists at least one building to its left, right, top, and bottom.

So all we really need to do is to keep track of the extreme coordinates for each row and column.

I did that with 2 arrays:

  • x_axes: This array keeps track of the minimum and maximum column indices for each row.
  • y_axes: This array keeps track of the minimum and maximum row indices for each column.

Solution in Python


class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        m, n = 0, 0
        
        for x, y in buildings:
            m = max(m, x + 2) 
            n = max(n, y + 2)

        print(m, n)

        x_axes = [[inf,-inf] for _ in range(m)]
        y_axes = [[inf,-inf] for _ in range(n)]

        for x, y in buildings:
            # old_left_col, old_right_col
            olc, orc = x_axes[x] 
            x_axes[x] = [min(olc, y), max(orc, y)]
            
            # old_top_row, old_bottom_row
            otr, obr = y_axes[y] 
            y_axes[y] = [min(otr, x), max(obr, x)]

        res = 0

        for x, y in buildings:
            # left_col, right_col
            lc, rc = x_axes[x]
            # top_row, bottom_row
            tr, br = y_axes[y]

            if lc < y < rc and tr < x < br:
                res += 1

        return res

Complexity

  • Time: $O(n)$

  • Space: $O(m + n)$
    Where m is the number of rows and n is the number of columns.

And we are done.