Skip to main content
Talentd

Count Covered Buildings - Solution & Explanation

MediumArrayHash TableSorting12 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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.

Approach Overview

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.

Solution

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.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair ComparisonO(n²)O(1)Useful for understanding the coverage condition or when input size is very small
Hash Table + Sorting SweepO(n log n)O(n)General optimal solution for large inputs; sorting allows a single pass coverage check

Video Solution

Count Covered Buildings | Simplest Intuition | Dry Run | Leetcode 3531 | codestorywithMIK • codestorywithMIK • 6,196 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Covered Buildings easy or hard?
Count Covered Buildings is generally considered a medium-level problem. The main challenge is recognizing the interval containment pattern and applying sorting correctly. Once the intervals are ordered properly, the remaining logic is a straightforward linear scan.
Count Covered Buildings Python/Java solution
In Python or Java, store the buildings in an array of intervals, sort them with a custom comparator (start ascending, end descending), and iterate while maintaining the maximum end value. Increment a counter whenever an interval's end is within that range. The implementation is concise and runs in O(n log n) time.
How to solve Count Covered Buildings in O(n log n)?
First sort the buildings by start ascending and end descending. Maintain a variable storing the largest end value encountered. During the traversal, if the current building's end is less than or equal to this value, it means a previous building fully covers it; otherwise update the maximum end. This reduces the problem to a single sweep after sorting.
What is the best approach for Count Covered Buildings?
The best approach sorts the buildings by start coordinate ascending and end coordinate descending, then scans the list while tracking the maximum end seen so far. If the current building's end is less than or equal to that maximum, it is fully covered by a previous building. This method runs in O(n log n) time due to sorting and uses O(n) space if auxiliary structures are used.
Is Count Covered Buildings asked at Google/Amazon/Meta?
Interval coverage and containment problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants such as removing covered intervals or counting nested ranges are common because they test sorting strategies and efficient scanning logic.
What data structure is used in Count Covered Buildings?
The main data structures are arrays to store building intervals and sorting utilities to order them correctly. A hash table may also be used to group or track intervals with identical start points. The key algorithmic idea is the sorted interval sweep rather than a complex structure.
What is the time complexity of Count Covered Buildings?
The optimal solution runs in O(n log n) time because the intervals must be sorted before scanning. After sorting, a single linear pass determines which buildings are covered by comparing each interval's end with the maximum end seen so far. Space complexity is typically O(1) to O(n) depending on whether additional structures such as a hash table are used.

Ready to solve this problem?

Practice Count Covered Buildings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays