3819. Count Covered Buildings

Array Hash Table Sorting

Problem - Count Covered Buildings

Medium

You are given a positive integer n, representing an n x n city. You are also given a 2D grid buildings, where buildings[i] = [x, y] denotes a unique building located at coordinates [x, y].

A building is covered if there is at least one building in all four directions: left, right, above, and below.

Return the number of covered buildings.

 

Example 1:

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

Output: 1

Explanation:

• Only building [2,2] is covered as it has at least one building:
  • above ([1,2])
  • below ([3,2])
  • left ([2,1])
  • right ([2,3])
• Thus, the count of covered buildings is 1.

Example 2:

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

Output: 0

Explanation:

• No building has at least one building in all four directions.

Example 3:

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

Output: 1

Explanation:

• Only building [3,3] is covered as it has at least one building:
  • above ([1,3])
  • below ([5,3])
  • left ([3,2])
  • right ([3,5])
• Thus, the count of covered buildings is 1.

 

Constraints:

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

Solutions

Python3

class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        x_graph = defaultdict(list)
        y_graph = defaultdict(list)
        for x, y in buildings:
            x_graph[x].append(y)
            y_graph[y].append(x)
        for x in x_graph:
            x_graph[x].sort()
        for y in y_graph:
            y_graph[y].sort()

        result = 0
        for x, y in buildings:
            x_list, y_list = x_graph[x], y_graph[y]
            if y_list[0] < x < y_list[-1] and x_list[0] < y < x_list[-1]:
                result += 1
        return result

Submission Stats:

• Runtime: 370 ms (99.16%)
• Memory: 60.9 MB (46.22%)