# Count Covered Buildings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-covered-buildings)
Canonical: https://scaleengineer.com/dsa/problems/count-covered-buildings
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## 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:**

![](https://assets.glich.co/dsa/count-covered-buildings/image0.jpg)

**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:**

![](https://assets.glich.co/dsa/count-covered-buildings/image1.jpg)

**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:**

![](https://assets.glich.co/dsa/count-covered-buildings/image2.jpg)

**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**.

# Approaches
## Brute Force Iteration
This approach iterates through every building and, for each one, scans all other buildings to check for the presence of neighbors in the four required directions (above, below, left, right).
**Time:** O(B^2) - Where B is the number of buildings. For each of the B buildings, we iterate through all other B-1 buildings, leading to a quadratic time complexity. · **Space:** O(1) - We only use a constant number of variables to keep track of the state for the current building being checked.
**Pros:** Simple to understand and implement.; Requires no extra space apart from a few variables.
**Cons:** Extremely inefficient for large inputs.; Will result in a 'Time Limit Exceeded' error on platforms with strict time limits for the given constraints.
### Explanation
The brute-force method is the most straightforward way to solve the problem. For every single building, we perform a complete scan of the entire list of buildings to find if it has at least one neighbor in each of the four cardinal directions. While simple to conceptualize, its performance degrades quadratically with the number of buildings, making it unsuitable for large datasets.

```java
class Solution {
    public int countCoveredBuildings(int n, int[][] buildings) {
        int coveredCount = 0;
        int numBuildings = buildings.length;

        for (int i = 0; i < numBuildings; i++) {
            int x1 = buildings[i][0];
            int y1 = buildings[i][1];

            boolean hasAbove = false;
            boolean hasBelow = false;
            boolean hasLeft = false;
            boolean hasRight = false;

            for (int j = 0; j < numBuildings; j++) {
                if (i == j) continue;

                int x2 = buildings[j][0];
                int y2 = buildings[j][1];

                if (y1 == y2) { // Same column
                    if (x2 < x1) hasAbove = true;
                    if (x2 > x1) hasBelow = true;
                }
                if (x1 == x2) { // Same row
                    if (y2 < y1) hasLeft = true;
                    if (y2 > y1) hasRight = true;
                }
            }

            if (hasAbove && hasBelow && hasLeft && hasRight) {
                coveredCount++;
            }
        }
        return coveredCount;
    }
}
```
### Algorithm
*   Initialize a counter `coveredBuildings` to 0.
*   For each building `b1` at `(x, y)` in the input list:
*   Initialize four boolean flags: `hasLeft`, `hasRight`, `hasAbove`, `hasBelow` to `false`.
*   Iterate through every other building `b2` at `(x2, y2)` in the list.
*   Compare `b2` with `b1`:
    *   If `x2 == x` and `y2 < y`, set `hasLeft = true`.
    *   If `x2 == x` and `y2 > y`, set `hasRight = true`.
    *   If `y2 == y` and `x2 < x`, set `hasAbove = true`.
    *   If `y2 == y` and `x2 > x`, set `hasBelow = true`.
*   After checking all other buildings, if all four flags are `true`, increment `coveredBuildings`.
*   Return `coveredBuildings`.

## Grouping by Row/Column and Sorting
This approach improves upon the brute-force method by pre-processing the building locations. We group buildings by their row and column and then sort these groups. This allows for efficient searching of neighbors using binary search instead of a linear scan.
**Time:** O(B log B) - Where B is the number of buildings. Populating the maps is O(B). The dominant operation is sorting the lists within the maps, which can take up to O(B log B) in total. The final check involves B binary searches, also contributing to the O(B log B) complexity. · **Space:** O(B) - The maps store each building's coordinates once, so the space is proportional to the number of buildings.
**Pros:** Significantly faster than the brute-force approach.; Efficient enough to pass the given constraints.
**Cons:** Requires additional space for the maps.; The sorting step adds a logarithmic factor to the time complexity.
### Explanation
To avoid the O(B^2) complexity, we can pre-process the data. By grouping all buildings by their row and column into HashMaps, we can quickly access all buildings on the same horizontal or vertical line. After grouping, we sort the buildings within each group. Now, for any given building `(x, y)`, we can use binary search on the sorted list for its row `x` to see if there are buildings with smaller and larger `y` coordinates. Similarly, we check its column `y` for buildings with smaller and larger `x` coordinates. This reduces the search for neighbors from a linear scan to a logarithmic one.

```java
import java.util.*;

class Solution {
    public int countCoveredBuildings(int n, int[][] buildings) {
        Map<Integer, List<Integer>> rows = new HashMap<>();
        Map<Integer, List<Integer>> cols = new HashMap<>();

        for (int[] building : buildings) {
            int x = building[0];
            int y = building[1];
            rows.computeIfAbsent(x, k -> new ArrayList<>()).add(y);
            cols.computeIfAbsent(y, k -> new ArrayList<>()).add(x);
        }

        for (List<Integer> list : rows.values()) {
            Collections.sort(list);
        }
        for (List<Integer> list : cols.values()) {
            Collections.sort(list);
        }

        int coveredCount = 0;
        for (int[] building : buildings) {
            int x = building[0];
            int y = building[1];

            List<Integer> rowList = rows.get(x);
            List<Integer> colList = cols.get(y);

            int yIndex = Collections.binarySearch(rowList, y);
            boolean hasLeft = yIndex > 0;
            boolean hasRight = yIndex < rowList.size() - 1;

            int xIndex = Collections.binarySearch(colList, x);
            boolean hasAbove = xIndex > 0;
            boolean hasBelow = xIndex < colList.size() - 1;

            if (hasLeft && hasRight && hasAbove && hasBelow) {
                coveredCount++;
            }
        }
        return coveredCount;
    }
}
```
### Algorithm
*   Create two maps: `rows` to group buildings by row, and `cols` to group by column. `rows` will map a row index `x` to a list of column indices `y`, and `cols` will map a column index `y` to a list of row indices `x`.
*   Populate these maps by iterating through the `buildings` array once.
*   Sort the lists of coordinates within each map entry.
*   Initialize a counter `coveredBuildings` to 0.
*   Iterate through each building `(x, y)` again.
*   For the current building:
    *   Look up the sorted list of columns for its row `x` in the `rows` map. Use binary search to find the position of `y`. If `y` is not the first and not the last element, it has both a left and a right neighbor.
    *   Look up the sorted list of rows for its column `y` in the `cols` map. Use binary search to find the position of `x`. If `x` is not the first and not the last element, it has both an above and a below neighbor.
*   If the building has neighbors in all four directions, increment `coveredBuildings`.
*   Return `coveredBuildings`.

## Linear Time Solution with Min/Max Pre-processing
This is the most efficient approach. Instead of storing and sorting lists of all coordinates for each row and column, we only need to know the minimum and maximum coordinate in each row and column. This simplifies the check for neighbors to a simple comparison, achieving a linear time solution.
**Time:** O(B) - Where B is the number of buildings. We perform two linear passes over the `buildings` array. Each map operation (get, put) takes O(1) on average, resulting in an overall linear time complexity. · **Space:** O(B) - In the worst case, each building could be in a unique row and column, leading to up to B entries in each of the four maps. The space is proportional to the number of unique rows and columns, which is at most B.
**Pros:** Optimal time complexity.; The logic is clear and avoids complex operations like sorting.
**Cons:** Requires extra space for four maps, which could be significant if the number of unique rows and columns is large.
### Explanation
This optimal solution refines the pre-processing idea. A building is covered if and only if it is not on the 'edge' of the buildings in its row and column. This means for a building at `(x, y)` to be covered, there must be other buildings in the same row `x` with both smaller and larger `y` coordinates, and other buildings in the same column `y` with both smaller and larger `x` coordinates. We can determine this by finding the minimum and maximum coordinates for each row and column in a single pass. Then, in a second pass, we can check each building against these pre-computed min/max values in constant time.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int countCoveredBuildings(int n, int[][] buildings) {
        Map<Integer, Integer> minColInRow = new HashMap<>();
        Map<Integer, Integer> maxColInRow = new HashMap<>();
        Map<Integer, Integer> minRowInCol = new HashMap<>();
        Map<Integer, Integer> maxRowInCol = new HashMap<>();

        // First pass: find min/max for each row and column
        for (int[] building : buildings) {
            int x = building[0];
            int y = building[1];

            minColInRow.put(x, Math.min(minColInRow.getOrDefault(x, Integer.MAX_VALUE), y));
            maxColInRow.put(x, Math.max(maxColInRow.getOrDefault(x, Integer.MIN_VALUE), y));
            minRowInCol.put(y, Math.min(minRowInCol.getOrDefault(y, Integer.MAX_VALUE), x));
            maxRowInCol.put(y, Math.max(maxRowInCol.getOrDefault(y, Integer.MIN_VALUE), x));
        }

        int coveredCount = 0;
        // Second pass: check each building
        for (int[] building : buildings) {
            int x = building[0];
            int y = building[1];

            boolean hasLeft = y > minColInRow.get(x);
            boolean hasRight = y < maxColInRow.get(x);
            boolean hasAbove = x > minRowInCol.get(y);
            boolean hasBelow = x < maxRowInCol.get(y);

            if (hasLeft && hasRight && hasAbove && hasBelow) {
                coveredCount++;
            }
        }

        return coveredCount;
    }
}
```
### Algorithm
*   A building at `(x, y)` is covered if it's not an extremal building in its row and column. That is, `y` is not the minimum or maximum `y` in row `x`, and `x` is not the minimum or maximum `x` in column `y`.
*   Create four maps to store the extremal coordinates: `minColInRow`, `maxColInRow`, `minRowInCol`, `maxRowInCol`.
*   Iterate through the `buildings` array once to populate these four maps. For each building `(x, y)`, update the min/max values for row `x` and column `y`.
*   Initialize a counter `coveredBuildings` to 0.
*   Iterate through the `buildings` array a second time.
*   For each building `(x, y)`:
    *   Check if it has a left neighbor: `y > minColInRow.get(x)`.
    *   Check if it has a right neighbor: `y < maxColInRow.get(x)`.
    *   Check if it has an above neighbor: `x > minRowInCol.get(y)`.
    *   Check if it has a below neighbor: `x < maxRowInCol.get(y)`.
*   If all four conditions are met, increment `coveredBuildings`.
*   Return `coveredBuildings`.

# Solutions
### Java

```java
class Solution {
public
  int countCoveredBuildings(int n, int[][] buildings) {
    Map<Integer, List<Integer>> g1 = new HashMap<>();
    Map<Integer, List<Integer>> g2 = new HashMap<>();
    for (int[] building : buildings) {
      int x = building[0], y = building[1];
      g1.computeIfAbsent(x, k->new ArrayList<>()).add(y);
      g2.computeIfAbsent(y, k->new ArrayList<>()).add(x);
    }
    for (var e : g1.entrySet()) {
      Collections.sort(e.getValue());
    }
    for (var e : g2.entrySet()) {
      Collections.sort(e.getValue());
    }
    int ans = 0;
    for (int[] building : buildings) {
      int x = building[0], y = building[1];
      List<Integer> l1 = g1.get(x);
      List<Integer> l2 = g2.get(y);
      if (l2.get(0) < x && x < l2.get(l2.size() - 1) && l1.get(0) < y &&
          y < l1.get(l1.size() - 1)) {
        ans++;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countCoveredBuildings(int n, vector<vector<int>> &buildings) {
    unordered_map<int, vector<int>> g1;
    unordered_map<int, vector<int>> g2;
    for (const auto &building : buildings) {
      int x = building[0], y = building[1];
      g1[x].push_back(y);
      g2[y].push_back(x);
    }
    for (auto &e : g1) {
      sort(e.second.begin(), e.second.end());
    }
    for (auto &e : g2) {
      sort(e.second.begin(), e.second.end());
    }
    int ans = 0;
    for (const auto &building : buildings) {
      int x = building[0], y = building[1];
      const vector<int> &l1 = g1[x];
      const vector<int> &l2 = g2[y];
      if (l2[0] < x && x < l2[l2.size() - 1] && l1[0] < y &&
          y < l1[l1.size() - 1]) {
        ans++;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int: g1 = defaultdict(list) g2 = defaultdict(list) for x, y in buildings: g1[x]. append(y) g2[y]. append(x) for x in g1: g1[x]. sort() for y in g2: g2[y]. sort() ans = 0 for x, y in buildings: l1 = g1[x] l2 = g2[y] if l2[0] < x < l2[- 1] and l1[0] < y < l1[- 1]: ans += 1 return ans

```