Count Covered Buildings

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.

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

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.

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