3531.Count_Covered_Buildings(Medium).md

3531. Count Covered Buildings (Medium)

Date and Time: Apr 26, 2025

Link: https://leetcode.com/problems/count-covered-buildings

Walk-through:

1. Use row, col dictionaries to save each pt's r, c. rows: {r: [cols]}, cols: {c: [rows]}. Every point with the same r, I will save their c into rows dictionary, same thing for cols.

2. Sort rows, cols, so later we can use binary search to find pts.

3. For each pt, we apply binary search to find each pt's (r, c), we first check r on cols[c], find its index, then we check if index > 0 so we know r's left exists in cols[c], check if index < len(cols[c] -1 ) to know r's right exists in cols[c]. Same thing to check this pt's top and bottom.

Python:

class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        # Q: Return the number of covered buildings
        # S: 1. Add each pt into rows, cols dictionary, every pt with the same row will have a list of y-axis, the same col with have a list of x-axis
        # 2. Sort rows and cols
        # 3. For each building, check its four directions, for each axis, I can run binary search on this pt's x and y, then if the index of x/y is not the first or the last index in the corresponding's dictionary, we know this building has four directions
        # TC: O(nlogn), SC: O(n)

        # 1. Build two dictionaries
        rows, cols = collections.defaultdict(list), collections.defaultdict(list)
        for r, c in buildings:
            rows[r].append(c)
            cols[c].append(r)
        # 2. Sort rows and cols
        for _, lst in rows.items():
            lst.sort()
        for _, lst in cols.items():
            lst.sort()
        # 3. Check each building's four directions by binary search on its index
        ans = 0
        def bs(lst, pt):
            l, r = 0, len(lst)-1
            while l <= r:
                m = (l+r) // 2
                if lst[m] == pt:
                    return m
                elif lst[m] < pt:
                    l = m + 1
                else:
                    r = m - 1
        # Check each building's x, y index
        for r, c in buildings:
            # Find x, y index of this pt
            y = bs(rows[r], c)
            x = bs(cols[c], r)
            # If their index is not the first or the last in their list, we have other points in four directions
            if 0 < x < len(cols[c])-1 and 0 < y < len(rows[r])-1:
                ans += 1
        return ans

Time Complexity: $O(nlog(n))$
Space Complexity: $O(n)$

Java

class Solution {
    /* 
    1. Save each pt's row, col into two dictionaries {r: [cols]}
    2. Sort each rows, cols dictionary
    3. Check each pt's four directions by binary sesarch to find pt's x, y index
    TC: O(nlogn), SC: O(n)
    */
    Map<Integer, List<Integer>> rows = new HashMap<>();
    Map<Integer, List<Integer>> cols = new HashMap<>();

    private int bs(List<Integer> lst, int target) {
        int l = 0;
        int r = lst.size() - 1;
        while (l <= r) {
            int m = (l+r) / 2;
            if (lst.get(m) == target) {
                return m;
            } else if (lst.get(m) < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }

    public int countCoveredBuildings(int n, int[][] buildings) {
        // 1. Add pt to dictionaries
        for (int[] building: buildings) {
            int r = building[0];
            int c = building[1];
            // Add to rows
            List<Integer> row_list = rows.getOrDefault(r, new ArrayList<>());
            row_list.add(c);
            rows.put(r, row_list);
            // Add to cols
            List<Integer> col_list = cols.getOrDefault(c, new ArrayList<>());
            col_list.add(r);
            cols.put(c, col_list);
        }
        // 2. Sort rows, cols
        for (Map.Entry<Integer, List<Integer>> entry : rows.entrySet()) {
            Collections.sort(entry.getValue()); // Sort the list in place
        }
        for (Map.Entry<Integer, List<Integer>> entry : cols.entrySet()) {
            Collections.sort(entry.getValue()); // Sort the list in place
        }
        // 3. Run Binary Search on each pt's x, y index to check four directions
        int ans = 0;
        for (int[] building: buildings) {
            int r = building[0];
            int c = building[1];
            // Get x, y index
            int x = bs(cols.get(c), r);
            int y = bs(rows.get(r), c);
            if (0 < x && x < cols.get(c).size()-1 && 0 < y && y < rows.get(r).size()-1) {
                ans++;
            }
        }
        return ans;
    }
}