Count Covered Buildings
MedPrompt
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])
- above (
- 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])
- above (
- Thus, the count of covered buildings is 1.
Constraints:
2 <= n <= 1051 <= buildings.length <= 105buildings[i] = [x, y]1 <= x, y <= n- All coordinates of
buildingsare 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:
rowsto group buildings by row, andcolsto group by column.rowswill map a row indexxto a list of column indicesy, andcolswill map a column indexyto a list of row indicesx. - Populate these maps by iterating through the
buildingsarray once. - Sort the lists of coordinates within each map entry.
- Initialize a counter
coveredBuildingsto 0. - Iterate through each building
(x, y)again. - For the current building:
- Look up the sorted list of columns for its row
xin therowsmap. Use binary search to find the position ofy. Ifyis 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
yin thecolsmap. Use binary search to find the position ofx. Ifxis not the first and not the last element, it has both an above and a below neighbor.
- Look up the sorted list of columns for its row
- 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
Solution
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.