Problem

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

1
2
3
4
5
6
7
8
9
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

1
2
3
4
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

1
2
3
4
5
6
7
8
9
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 <= 10^5
  • 1 <= buildings.length <= 10^5
  • buildings[i] = [x, y]
  • 1 <= x, y <= n
  • All coordinates of buildings are unique.

Examples

Solution

Method 1 – Hash Set Lookup

Intuition

A building is covered if there is at least one building in all four directions (left, right, above, below). For each building, we can check if the positions directly above, below, left, and right are also buildings. Using a set for fast lookup makes this efficient.

Approach

  1. Store all building coordinates in a set for O(1) lookup.
  2. For each building, check if the four neighbors (up, down, left, right) exist in the set.
  3. If all four exist, increment the answer.
  4. Return the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int countCoveredBuildings(int n, vector<vector<int>>& buildings) {
        set<pair<int, int>> s;
        for (auto& b : buildings) s.insert({b[0], b[1]});
        int ans = 0;
        for (auto& b : buildings) {
            int x = b[0], y = b[1];
            if (s.count({x-1, y}) && s.count({x+1, y}) && s.count({x, y-1}) && s.count({x, y+1}))
                ans++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func countCoveredBuildings(n int, buildings [][]int) int {
    s := map[[2]int]bool{}
    for _, b := range buildings {
        s[[2]int{b[0], b[1]}] = true
    }
    ans := 0
    for _, b := range buildings {
        x, y := b[0], b[1]
        if s[[2]int{x-1, y}] && s[[2]int{x+1, y}] && s[[2]int{x, y-1}] && s[[2]int{x, y+1}] {
            ans++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int countCoveredBuildings(int n, int[][] buildings) {
        Set<String> s = new HashSet<>();
        for (int[] b : buildings) s.add(b[0] + "," + b[1]);
        int ans = 0;
        for (int[] b : buildings) {
            int x = b[0], y = b[1];
            if (s.contains((x-1)+","+y) && s.contains((x+1)+","+y) && s.contains(x+","+(y-1)) && s.contains(x+","+(y+1)))
                ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    fun countCoveredBuildings(n: Int, buildings: Array<IntArray>): Int {
        val s = buildings.map { it[0] to it[1] }.toSet()
        var ans = 0
        for ((x, y) in buildings) {
            if (s.contains(x-1 to y) && s.contains(x+1 to y) && s.contains(x to y-1) && s.contains(x to y+1))
                ans++
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
class Solution:
    def countCoveredBuildings(self, n: int, buildings: list[list[int]]) -> int:
        s = set(map(tuple, buildings))
        ans = 0
        for x, y in buildings:
            if (x-1, y) in s and (x+1, y) in s and (x, y-1) in s and (x, y+1) in s:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
use std::collections::HashSet;
impl Solution {
    pub fn count_covered_buildings(n: i32, buildings: Vec<Vec<i32>>) -> i32 {
        let s: HashSet<(i32, i32)> = buildings.iter().map(|b| (b[0], b[1])).collect();
        let mut ans = 0;
        for b in &buildings {
            let (x, y) = (b[0], b[1]);
            if s.contains(&(x-1, y)) && s.contains(&(x+1, y)) && s.contains(&(x, y-1)) && s.contains(&(x, y+1)) {
                ans += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    countCoveredBuildings(n: number, buildings: number[][]): number {
        const s = new Set(buildings.map(b => `${b[0]},${b[1]}`));
        let ans = 0;
        for (const [x, y] of buildings) {
            if (
                s.has(`${x-1},${y}`) &&
                s.has(`${x+1},${y}`) &&
                s.has(`${x},${y-1}`) &&
                s.has(`${x},${y+1}`)
            ) ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(m), where m is the number of buildings, since each lookup is O(1).
  • 🧺 Space complexity: O(m), for storing the set of buildings.