3531. Count Covered Buildings

Source: Dev.to

Problem Description

You are given a positive integer n, representing an n × n city.
You are also given a 2D array 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.

Examples

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 because it has at least one building above ([1,2]), below ([3,2]), left ([2,1]), and right ([2,3]).

Example 2

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

Explanation:
No building has neighbors 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 (above [1,3], below [5,3], left [3,2], right [3,5]).

Constraints

• 2 ≤ n ≤ 10⁵
• 1 ≤ buildings.length ≤ 10⁵
• buildings[i] = [x, y]
• 1 ≤ x, y ≤ n
• All coordinates of buildings are unique.

Hint

Group buildings with the same x or y value together, and sort each group.
In each sorted list, the buildings that are not at the first or last positions are covered in that direction.

Solution Overview

We need to determine for each building whether it has at least one neighbor in all four directions.
A naïve O(m²) check (where m is the number of buildings) is too slow.
Instead, we:

1. Group buildings by column (x) and by row (y).
2. Sort each group.
3. For each building, check its position within the sorted column and row to infer the presence of neighbors above/below and left/right.
4. Count buildings that have neighbors in all four directions.

Algorithm Details

Grouping by coordinates

• xMap[x] → list of y values of buildings in column x.
• yMap[y] → list of x values of buildings in row y.

Determining vertical coverage (above / below)

For each column x in xMap:

1. Sort the list of y values.
2. For each building (x, y) in that column:
   • It has a building above if it is not the smallest y.
   • It has a building below if it is not the largest y.

Determining horizontal coverage (left / right)

For each row y in yMap:

1. Sort the list of x values.
2. For each building (x, y) in that row:
   • It has a building left if it is not the smallest x.
   • It has a building right if it is not the largest x.

Counting covered buildings

Maintain a status map for each building with four boolean flags (above, below, left, right).
After processing both dimensions, a building is counted if all four flags are true.

Complexity Analysis

• Time: O(m log m), where m = buildings.length.

  • Grouping: O(m)
  • Sorting each group (total across all groups): O(m log m)
  • Scanning groups to set flags: O(m)

• Space: O(m) for the grouping maps and status storage.

Reference Implementation (PHP)

// list of y, y => list of x
$xMap = [];
$yMap = [];

// Store each building's index for quick status updates
$indexMap = []; // "x,y" => idx
foreach ($buildings as $idx => $b) {
    [$x, $y] = $b;
    $xMap[$x][] = $y;
    $yMap[$y][] = $x;
    $indexMap["$x,$y"] = $idx;
}

// Status flags: each entry is ['above'=>false,'below'=>false,'left'=>false,'right'=>false]
$status = array_fill(0, $m, [
    'above' => false,
    'below' => false,
    'left'  => false,
    'right' => false,
]);

// Vertical check (above / below)
foreach ($xMap as $x => $ys) {
    sort($ys, SORT_NUMERIC);
    $cnt = count($ys);
    foreach ($ys as $pos => $y) {
        $idx = $indexMap["$x,$y"];
        if ($pos > 0) {
            $status[$idx]['above'] = true;   // there is a smaller y (above)
        }
        if ($pos < $cnt - 1) {
            $status[$idx]['below'] = true;   // there is a larger y (below)
        }
    }
}

// Horizontal check (left / right)
foreach ($yMap as $y => $xs) {
    sort($xs, SORT_NUMERIC);
    $cnt = count($xs);
    foreach ($xs as $pos => $x) {
        $idx = $indexMap["$x,$y"];
        if ($pos > 0) {
            $status[$idx]['left'] = true;    // smaller x exists
        }
        if ($pos < $cnt - 1) {
            $status[$idx]['right'] = true;   // larger x exists
        }
    }
}

// Count covered buildings
$covered = 0;
foreach ($status as $flags) {
    if ($flags['above'] && $flags['below'] && $flags['left'] && $flags['right']) {
        $covered++;
    }
}
return $covered;