LeetCode 3531 - Count Covered Buildings

The task asks us to count how many buildings in a given set are covered in all four cardinal directions: left, right, above, and below, within an n x n grid. Each building is represented by a coordinate pair [x, y], and all coordinates are unique.

leetcodemediumarrayhash-tablesorting

LeetCode Problem 3531

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sorting

Solution

Problem Understanding

The task asks us to count how many buildings in a given set are covered in all four cardinal directions: left, right, above, and below, within an n x n grid. Each building is represented by a coordinate pair [x, y], and all coordinates are unique.

A building is considered covered if it satisfies two independent conditions. First, in its row (fixed y), there must exist at least one building strictly to its left (smaller x) and at least one strictly to its right (larger x). Second, in its column (fixed x), there must exist at least one building strictly above (smaller y) and at least one strictly below (larger y).

The grid size n can be as large as 10^5, and there can be up to 10^5 buildings, which implies that any solution that checks each building against all others will be too slow. This immediately suggests that we need a preprocessing strategy to answer directional existence queries efficiently.

Edge cases include situations where there are fewer than three buildings in a row or column, making it impossible for any building to be covered. Another edge case is when buildings form a straight line horizontally or vertically, which guarantees zero covered buildings because one of the required directional constraints will always fail.

Approaches

Brute Force Approach

The brute-force idea is straightforward. For each building, we scan all other buildings and check whether there exists at least one building with a smaller and larger x in the same row, and similarly at least one with smaller and larger y in the same column. This works because it directly enforces the definition of “covered.”

However, this approach is too slow because for each of the m buildings, we may scan all other m buildings, leading to quadratic time complexity. With m up to 10^5, this is not feasible.

Key Insight for Optimization

Instead of checking every pair of buildings, we observe that for each row and column, we only need to know the minimum and maximum coordinate values.

For a fixed row y, if we know the smallest and largest x values present in that row, then any building whose x is strictly between these two extremes automatically has at least one building to its left and right.

Similarly, for a fixed column x, if we track the smallest and largest y values, any building whose y lies strictly between them automatically has at least one building above and below.

This reduces the problem to a preprocessing step followed by constant-time checks per building.

Complexity Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(m²) O(1) Check all pairs for each building
Optimal O(m) O(m) Precompute row and column extremes

Algorithm Walkthrough

The optimal solution relies on precomputing boundary information for each row and column.

  1. First, we iterate through all buildings and group information by rows and columns. For each row y, we track the minimum and maximum x values. For each column x, we track the minimum and maximum y values. This step compresses the entire dataset into directional summaries.
  2. We store this information using hash maps. One map represents rows (row_min_x, row_max_x), and another represents columns (col_min_y, col_max_y). Hash maps are chosen because coordinates are sparse and range up to 10^5, so direct indexing would be wasteful.
  3. After preprocessing, we iterate through each building [x, y].
  4. For each building, we check whether it is strictly inside its row boundaries by verifying row_min_x[y] < x < row_max_x[y].
  5. We also check whether it is strictly inside its column boundaries by verifying col_min_y[x] < y < col_max_y[x].
  6. If both conditions are satisfied, the building is considered covered, and we increment the result counter.
  7. Finally, we return the total count of covered buildings.

Why it works

The correctness comes from the fact that in any row, the existence of at least one smaller and one larger x is fully captured by knowing the minimum and maximum x. The same applies symmetrically for columns. Since coverage depends only on existence (not distance or count), extremal values are sufficient to represent all necessary information.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        row_min_x = defaultdict(lambda: float('inf'))
        row_max_x = defaultdict(lambda: float('-inf'))
        col_min_y = defaultdict(lambda: float('inf'))
        col_max_y = defaultdict(lambda: float('-inf'))
        
        for x, y in buildings:
            row_min_x[y] = min(row_min_x[y], x)
            row_max_x[y] = max(row_max_x[y], x)
            col_min_y[x] = min(col_min_y[x], y)
            col_max_y[x] = max(col_max_y[x], y)
        
        covered = 0
        
        for x, y in buildings:
            if (row_min_x[y] < x < row_max_x[y] and
                col_min_y[x] < y < col_max_y[x]):
                covered += 1
        
        return covered

Implementation Explanation

The code first builds four hash maps that store directional extremes. The first two track horizontal constraints per row, and the last two track vertical constraints per column. After preprocessing, each building is evaluated in constant time by checking whether it lies strictly between the extremes in both dimensions. If it does, it is counted as covered.

Go Solution

func countCoveredBuildings(n int, buildings [][]int) int {
    rowMinX := make(map[int]int)
    rowMaxX := make(map[int]int)
    colMinY := make(map[int]int)
    colMaxY := make(map[int]int)

    const inf = int(1e18)

    for _, b := range buildings {
        x, y := b[0], b[1]

        if _, ok := rowMinX[y]; !ok {
            rowMinX[y] = x
            rowMaxX[y] = x
        } else {
            if x < rowMinX[y] {
                rowMinX[y] = x
            }
            if x > rowMaxX[y] {
                rowMaxX[y] = x
            }
        }

        if _, ok := colMinY[x]; !ok {
            colMinY[x] = y
            colMaxY[x] = y
        } else {
            if y < colMinY[x] {
                colMinY[x] = y
            }
            if y > colMaxY[x] {
                colMaxY[x] = y
            }
        }
    }

    covered := 0

    for _, b := range buildings {
        x, y := b[0], b[1]

        if rowMinX[y] < x && x < rowMaxX[y] &&
            colMinY[x] < y && y < colMaxY[x] {
            covered++
        }
    }

    return covered
}

Go-specific Notes

In Go, maps do not support default values, so we explicitly check whether a key exists before updating min and max values. Unlike Python’s defaultdict, we manually initialize entries for each row and column. We also avoid overflow concerns by using int, which is sufficient given coordinate constraints.

Worked Examples

Example 1

Input: [[1,2],[2,2],[3,2],[2,1],[2,3]]

Row/column preprocessing yields:

Row y=2: minX = 1, maxX = 3

Column x=2: minY = 1, maxY = 3

Now evaluating each building:

Building Row condition Column condition Covered
(1,2) false true No
(2,2) true true Yes
(3,2) false true No
(2,1) true false No
(2,3) true false No

Final result is 1.

Example 2

Input: [[1,1],[1,2],[2,1],[2,2]]

Each row and column has only two points, so no building can have both a left/right and above/below neighbor.

Thus all buildings fail at least one condition, resulting in 0 covered buildings.

Example 3

Input: [[1,3],[3,2],[3,3],[3,5],[5,3]]

Row y=3: minX = 1, maxX = 5

Column x=3: minY = 2, maxY = 5

Only building (3,3) satisfies both strict inequalities in row and column checks, so only it is counted.

Complexity Analysis

Measure Complexity Explanation
Time O(m) One pass to compute bounds and one pass to evaluate each building
Space O(m) Hash maps store row and column aggregates

The solution is linear because each building is processed a constant number of times, and all lookups in hash maps are O(1) on average.

Test Cases

from solution import Solution

# Example 1
assert Solution().countCoveredBuildings(3, [[1,2],[2,2],[3,2],[2,1],[2,3]]) == 1

# Example 2
assert Solution().countCoveredBuildings(3, [[1,1],[1,2],[2,1],[2,2]]) == 0

# Example 3
assert Solution().countCoveredBuildings(5, [[1,3],[3,2],[3,3],[3,5],[5,3]]) == 1

# Single row line, no coverage possible
assert Solution().countCoveredBuildings(5, [[1,1],[2,1],[3,1]]) == 0

# Single column line, no coverage possible
assert Solution().countCoveredBuildings(5, [[2,1],[2,2],[2,3]]) == 0

# Minimal valid covered case requires at least 5 buildings forming cross
assert Solution().countCoveredBuildings(3, [[2,1],[2,3],[1,2],[3,2],[2,2]]) == 1
Test Why
Example 1 Basic positive case
Example 2 No possible coverage
Example 3 Single center coverage
horizontal line No vertical neighbors exist
vertical line No horizontal neighbors exist
cross shape Valid minimal covered configuration

Edge Cases

One important edge case is when all buildings lie in a single row. In this situation, every building fails the vertical condition because no building exists above or below any point. The algorithm handles this correctly because for each column, col_min_y[x] == col_max_y[x], making the strict inequality check fail.

Another edge case is when all buildings lie in a single column. Here, horizontal coverage fails for the same reason: row_min_x[y] == row_max_x[y], so no building can have both left and right neighbors.

A third edge case is when only two buildings exist in a row or column. Even if they are far apart, there is no intermediate building, so no point can satisfy both strict inequalities. The min/max logic correctly enforces this because equality between a point and an extreme boundary prevents it from being strictly inside.