How do you solve Count Covered Buildings on LeetCode?

Count Covered Buildings (LeetCode #3531) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Buildings must have neighbors in all four directions to be counted.

What is the time complexity of Count Covered Buildings?

The optimal solution for Count Covered Buildings runs in O(n) time and uses O(n) space. We only traverse the buildings a couple of times, leading to linear time complexity.

What is the brute force solution for Count Covered Buildings?

The brute force approach for Count Covered Buildings is Brute Force, with O(n²) time complexity and O(1) space complexity. Check each building and see if there are buildings in all four directions. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Count Covered Buildings?

Count Covered Buildings uses the following concepts: Array, Hash Table, Sorting. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Count Covered Buildings?

Explain your thought process clearly. Discuss time and space complexities. Consider edge cases during your explanation.

What are common mistakes when solving Count Covered Buildings?

Not considering edge cases where buildings are on the edge of the grid. Confusing the count of buildings with their positions.

#3531

Count Covered Buildings

Medium

ArrayHash TableSortingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Group buildings by their coordinates and check for coverage efficiently using sets.

⚙️

Algorithm

3 steps

1Step 1: Create two dictionaries to group buildings by their x and y coordinates.
2Step 2: For each building, check if it has buildings in all four directions using the dictionaries.
3Step 3: Count and return the number of covered buildings.

solution.py10 lines

1def countCoveredBuildings(n, buildings):
2    x_map, y_map = {}, {}
3    for x, y in buildings:
4        x_map.setdefault(x, []).append(y)
5        y_map.setdefault(y, []).append(x)
6    count = 0
7    for x, y in buildings:
8        if len(x_map[x]) > 1 and len(y_map[y]) > 1:
9            count += 1
10    return count

ℹ

Complexity note: We only traverse the buildings a couple of times, leading to linear time complexity.

1Buildings must have neighbors in all four directions to be counted.
2Grouping by coordinates allows efficient checking.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.