Count Covered Buildings

Count Covered Buildings

What is this problem about?

The Count Covered Buildings interview question (likely a variation of an interval coverage problem) asks you to determine how many buildings are "covered" or "hidden" based on their heights and positions. Usually, a building is considered covered if there is a taller building to its left or right within a certain range, or if it falls within the "shadow" of another building.

Why is this asked in interviews?

Amazon uses this Array interview pattern to test your ability to work with sorted data and intervals. It evaluates if you can use a "Sweep Line" algorithm or a Monotonic Stack to efficiently process linear data. It’s a "Medium" problem that requires identifying which buildings are redundant in a visibility or coverage set.

Algorithmic pattern used

This problem is typically solved using Sorting and a Greedy approach or a Sweep Line.

1. Sort the buildings by their starting position.
2. Maintain a variable max_reach or max_height seen so far.
3. As you iterate through the sorted buildings, check if the current building's extent is entirely within the max_reach of a previous taller building.
4. Alternatively, if it's about "visibility," use a monotonic stack to find buildings that are not blocked by taller ones.

Example explanation

Buildings: (pos: 1, height: 10), (pos: 2, height: 5), (pos: 5, height: 12)

1. Building 1 is at 1, height 10. max_height = 10.
2. Building 2 is at 2, height 5. Since its height (5) is less than the current max_height (10) and it's to the right, it might be considered "covered."
3. Building 3 is at 5, height 12. 12 > 10, so this building is NOT covered and becomes the new max_height.

Common mistakes candidates make

• Not Sorting: Trying to compare every building with every other building (O(N^2)).
• Overlooking Boundaries: Not correctly handling buildings that have the same height but different positions.
• Complex Geometry: Trying to use complex trigonometric visibility checks when a simple "max height" scan is sufficient.

Interview preparation tip

Whenever you see a problem involving "covering," "shadowing," or "merging," your first thought should be to Sort the input. Sorting by position or height usually simplifies the problem into a single-pass scan.