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 <= 10⁵
1 <= buildings.length <= 10⁵
buildings[i] = [x, y]
1 <= x, y <= n
All coordinates of buildings are unique.

Solutions

Solution 1: Hash Table + Sorting

We can group the buildings by their x-coordinates and y-coordinates, storing them in hash tables \(\text{g1}\) and \(\text{g2}\), respectively. Here, \(\text{g1[x]}\) represents all y-coordinates for buildings with x-coordinate \(x\), and \(\text{g2[y]}\) represents all x-coordinates for buildings with y-coordinate \(y\). Then, we sort these lists.

Next, we iterate through all buildings. For the current building \((x, y)\), we retrieve the corresponding y-coordinate list \(l_1\) from \(\text{g1}\) and the x-coordinate list \(l_2\) from \(\text{g2}\). We check the conditions to determine whether the building is covered. A building is covered if \(l_2[0] < x < l_2[-1]\) and \(l_1[0] < y < l_1[-1]\). If so, we increment the answer by one.

After finishing the iteration, we return the final answer.

The complexity is \(O(n \times \log n)\), and the space complexity is \(O(n)\), where \(n\) is the number of buildings.

Python3JavaC++GoTypeScriptRustC#

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

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;
    }
}

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;
    }
};

func countCoveredBuildings(n int, buildings [][]int) (ans int) {
    g1 := make(map[int][]int)
    g2 := make(map[int][]int)

    for _, building := range buildings {
        x, y := building[0], building[1]
        g1[x] = append(g1[x], y)
        g2[y] = append(g2[y], x)
    }

    for _, list := range g1 {
        sort.Ints(list)
    }
    for _, list := range g2 {
        sort.Ints(list)
    }

    for _, building := range buildings {
        x, y := building[0], building[1]
        l1 := g1[x]
        l2 := g2[y]

        if l2[0] < x && x < l2[len(l2)-1] && l1[0] < y && y < l1[len(l1)-1] {
            ans++
        }
    }
    return
}

function countCoveredBuildings(n: number, buildings: number[][]): number {
    const g1: Map<number, number[]> = new Map();
    const g2: Map<number, number[]> = new Map();

    for (const [x, y] of buildings) {
        if (!g1.has(x)) g1.set(x, []);
        g1.get(x)?.push(y);

        if (!g2.has(y)) g2.set(y, []);
        g2.get(y)?.push(x);
    }

    for (const list of g1.values()) {
        list.sort((a, b) => a - b);
    }
    for (const list of g2.values()) {
        list.sort((a, b) => a - b);
    }

    let ans = 0;

    for (const [x, y] of buildings) {
        const l1 = g1.get(x)!;
        const l2 = g2.get(y)!;

        if (l2[0] < x && x < l2[l2.length - 1] && l1[0] < y && y < l1[l1.length - 1]) {
            ans++;
        }
    }

    return ans;
}

use std::collections::HashMap;

impl Solution {
    pub fn count_covered_buildings(_n: i32, buildings: Vec<Vec<i32>>) -> i32 {
        let mut g1: HashMap<i32, Vec<i32>> = HashMap::new();
        let mut g2: HashMap<i32, Vec<i32>> = HashMap::new();

        for b in &buildings {
            let x = b[0];
            let y = b[1];
            g1.entry(x).or_insert(Vec::new()).push(y);
            g2.entry(y).or_insert(Vec::new()).push(x);
        }

        for v in g1.values_mut() {
            v.sort();
        }
        for v in g2.values_mut() {
            v.sort();
        }

        let mut ans: i32 = 0;

        for b in &buildings {
            let x = b[0];
            let y = b[1];

            let l1 = g1.get(&x).unwrap();
            let l2 = g2.get(&y).unwrap();

            if l2[0] < x && x < l2[l2.len() - 1] && l1[0] < y && y < l1[l1.len() - 1] {
                ans += 1;
            }
        }

        ans
    }
}

public class Solution {
    public int CountCoveredBuildings(int n, int[][] buildings) {
        var g1 = new Dictionary<int, List<int>>();
        var g2 = new Dictionary<int, List<int>>();

        foreach (var b in buildings) {
            int x = b[0], y = b[1];

            if (!g1.ContainsKey(x)) {
                g1[x] = new List<int>();
            }
            g1[x].Add(y);

            if (!g2.ContainsKey(y)) {
                g2[y] = new List<int>();
            }
            g2[y].Add(x);
        }

        foreach (var kv in g1) {
            kv.Value.Sort();
        }
        foreach (var kv in g2) {
            kv.Value.Sort();
        }

        int ans = 0;

        foreach (var b in buildings) {
            int x = b[0], y = b[1];
            var l1 = g1[x];
            var l2 = g2[y];

            if (l2[0] < x && x < l2[l2.Count - 1] &&
                l1[0] < y && y < l1[l1.Count - 1]) {
                ans++;
            }
        }

        return ans;
    }
}

3531. Count Covered Buildings

Description

Solutions

Solution 1: Hash Table + Sorting

Comments