Scale Engineer

Count Covered Buildings

Med
#3142Time: 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.
Algorithms
Sorting
Data structures
ArrayHash Table

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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

Complexity

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.

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem