Count covered buildings

Array Hash Table Sorting

58.8% acceptance

Feb 25, 2026

439

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

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_covered_buildings(_n: i32, buildings: Vec<Vec<i32>>) -> i32 {
    use std::collections::HashMap;

    // row -> sorted list of y values
    let mut rows: HashMap<i32, Vec<i32>> = HashMap::new();
    // col -> sorted list of x values
    let mut cols: HashMap<i32, Vec<i32>> = HashMap::new();

    for b in &buildings {
      let (x, y) = (b[0], b[1]);
      rows.entry(x).or_default().push(y);
      cols.entry(y).or_default().push(x);
    }

    for v in rows.values_mut() { v.sort_unstable(); }
    for v in cols.values_mut() { v.sort_unstable(); }

    let mut count = 0;
    for b in &buildings {
      let (x, y) = (b[0], b[1]);
      let row = rows.get(&x).unwrap();
      let col = cols.get(&y).unwrap();

      // left: same row, y' < y  => row[0] < y
      let has_left = row[0] < y;
      // right: same row, y' > y => row.last() > y
      let has_right = *row.last().unwrap() > y;
      // above: same col, x' < x => col[0] < x
      let has_above = col[0] < x;
      // below: same col, x' > x => col.last() > x
      let has_below = *col.last().unwrap() > x;

      if has_left && has_right && has_above && has_below {
        count += 1;
      }
    }

    count
  }
}