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:
[2,2] is covered as it has at least one building:
[1,2])[3,2])[2,1])[2,3])Example 2:
Input: n = 3, buildings = [[1,1],[1,2],[2,1],[2,2]]
Output: 0
Explanation:
Example 3:
Input: n = 5, buildings = [[1,3],[3,2],[3,3],[3,5],[5,3]]
Output: 1
Explanation:
[3,3] is covered as it has at least one building:
[1,3])[5,3])[3,2])[3,5])
Constraints:
2 <= n <= 1051 <= buildings.length <= 105 buildings[i] = [x, y]1 <= x, y <= nbuildings are unique.Problem Overview: You are given a list of buildings represented as ranges along a street. A building is considered covered if another building completely spans its range (its start is earlier or equal and its end is later or equal). The goal is to count how many buildings are covered by others.
Approach 1: Brute Force Interval Comparison (O(n²) time, O(1) space)
Compare every building with every other building. For each interval [l1, r1], iterate through all other intervals [l2, r2] and check whether l2 ≤ l1 and r2 ≥ r1. If such a building exists, mark the first one as covered. This approach uses simple nested iteration over the array of intervals and requires no extra data structures. It works for small inputs but quickly becomes slow because every pair of buildings must be checked.
Approach 2: Hash Table + Sorting Sweep (O(n log n) time, O(n) space)
Sort buildings by start coordinate ascending and end coordinate descending. This ordering ensures that larger covering intervals appear before the smaller ones that might be contained inside them. As you iterate through the sorted list, track the maximum end value seen so far. If the current building’s end is ≤ that maximum, it is fully covered by a previously processed building.
A small hash table can be used to track duplicates or group buildings with identical start points before the sweep, ensuring consistent ordering when multiple buildings begin at the same coordinate. The main work happens during the sorted traversal: update maxEnd whenever a larger interval appears and increment the covered count whenever the current end does not extend beyond it. Sorting dominates the complexity at O(n log n), while the scan itself runs in linear time.
This pattern is common in interval problems that involve containment checks. Sorting establishes a deterministic processing order, while a single pass maintains the best candidate for covering intervals.
Recommended for interviews: The sorting-based sweep is the expected solution. Interviewers want to see that you recognize the interval containment pattern and reduce the naive O(n²) comparisons to a single pass after sorting. Mentioning the brute force approach first shows understanding of the problem space, but implementing the sorted sweep demonstrates real algorithmic skill using sorting and interval reasoning.
We can group the buildings by their x-coordinates and y-coordinates, storing them in hash tables g1 and g2, respectively. Here, g1[x] represents all y-coordinates for buildings with x-coordinate x, and 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 g1 and the x-coordinate list l_2 from 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n²) | O(1) | Useful for understanding the coverage condition or when input size is very small |
| Hash Table + Sorting Sweep | O(n log n) | O(n) | General optimal solution for large inputs; sorting allows a single pass coverage check |
Count Covered Buildings | Simplest Intuition | Dry Run | Leetcode 3531 | codestorywithMIK • codestorywithMIK • 5,950 views views
Watch 9 more video solutions →Practice Count Covered Buildings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor