3531. Count Covered Buildings

Description

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

Solution: Hash Table

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number} n
 * @param {number[][]} buildings
 * @return {number}
 */
const countCoveredBuildings = function (n, buildings) {
  const rows = Array.from({ length: n + 1 }, () => ({ max: -1, min: n + 1 }));
  const cols = Array.from({ length: n + 1 }, () => ({ max: -1, min: n + 1 }));

  for (const [row, col] of buildings) {
    rows[row].max = Math.max(rows[row].max, col);
    rows[row].min = Math.min(rows[row].min, col);
    cols[col].max = Math.max(cols[col].max, row);
    cols[col].min = Math.min(cols[col].min, row);
  }

  return buildings.reduce((result, [row, col]) => {
    const isColCovered = col > rows[row].min && col < rows[row].max;
    const isRowCovered = row > cols[col].min && row < cols[col].max;
    const isCovered = isColCovered && isRowCovered;

    return result + (isCovered ? 1 : 0);
  }, 0);
};