Skip to content

Practice Count Covered Buildings

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#3531
LeetCode Problem

Count Covered Buildings

Problem Statement

Each pair in buildings identifies an occupied cell of an n-by-n city. Count buildings that have another building somewhere to their left and right in the same row, and another above and below in the same column. These neighbors need not be immediately adjacent. A diagonal building does not satisfy any of the four requirements. Approach: Record the minimum and maximum occupied column for each row, and the minimum and maximum occupied row for each column. A building is covered exactly when its coordinates lie strictly between both pairs of extrema. Two passes over the buildings take O(b) time and O(b) auxiliary space, where b is the number of buildings; scanning the whole city is unnecessary. Worked example: In the first input below, (2,2) has buildings on all four sides and is the only covered building. In the second, the three diagonal buildings cannot cover one another.

Source: Count Covered Buildings on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
n = 4, buildings = [[2,2],[1,2],[4,2],[2,1],[2,4]]
Output
1

# Example 2

Input
n = 3, buildings = [[1,1],[2,2],[3,3]]
Output
0

Constraints

The city side length n is between 2 and 100,000.
There are 1 to 100,000 buildings, with no repeated coordinate pair.
Each row and column coordinate is an integer from 1 through n.

How to solve Count Covered Buildings

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

A building has something to its left and right exactly when its column lies strictly between the smallest and largest occupied columns of its row, and likewise for its column, so four extreme values per row and column answer every building in constant time.

Why brute force is not enough

Comparing each building against every other for neighbors in four directions is O(b^2), about 10^10 for 100,000 buildings; an n by n city grid with n up to 100,000 would need 10^10 cells.

Approach

  1. In one pass, record for each row the minimum and maximum column seen and for each column the minimum and maximum row seen, using arrays of size n + 1 or hash maps.
  2. After this pass every occupied row's pair brackets all buildings in it, and the same holds for columns.
  3. In a second pass, a building at (x, y) is covered if y is strictly between the extremes of row x and x is strictly between the extremes of column y.
  4. Count the buildings passing both tests. Strictness guarantees a distinct building on each side because coordinates are unique.

Walkthrough of Example 1

n = 4, buildings = [[2,2],[1,2],[4,2],[2,1],[2,4]] → 1

  1. n is 4 and buildings are [[2,2],[1,2],[4,2],[2,1],[2,4]].
  2. Row extremes: row 1 columns 2 to 2, row 2 columns 1 to 4, row 4 columns 2 to 2. Column extremes: column 1 rows 2 to 2, column 2 rows 1 to 4, column 4 rows 2 to 2.
  3. Building (2,2): column 2 is strictly between 1 and 4 in row 2, and row 2 is strictly between 1 and 4 in column 2, so it is covered.
  4. Buildings (1,2) and (4,2) are in rows whose extremes are both 2, failing the row test; (2,1) and (2,4) are in columns whose extremes are both 2, failing the column test.
  5. Exactly one building is covered, the expected output of 1.

Time and space

Time O(b) · Space O(b). b is the number of buildings; two linear passes suffice, and the extremes occupy space proportional to distinct rows and columns, at most b each.

Interview pitfalls

  • Non-strict comparisons, which mark the first or last building in a line as covered.
  • Swapping the two coordinates, testing a row against the column extremes.
  • Allocating an n by n grid, which exhausts memory.
  • Forgetting that a row with one building has equal extremes and can never cover it.
  • Sorting per row and column and binary searching neighbors; correct but unnecessary.

Follow-up questions interviewers ask

  • How would you count buildings covered only horizontally or only vertically?
  • What if coverage required immediately adjacent neighbors rather than any building in that direction?
  • Could you support inserting buildings online and reporting the covered count after each one?

Further reading on the technique: Hash table

Related LeetCode Problems

Practice more problems similar to Count Covered Buildings.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.