LeetCode Entry

3531. Count Covered Buildings

11.12.2025 medium 2025 kotlin rust

Count surrounded dots on XY plane

3531. Count Covered Buildings medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1200

Problem TLDR

Count surrounded dots on XY plane #medium

Intuition

    // idea line sweep Y then X, collect in-betweens, intersect them

Line sweep: collect lines, sort each line, drop first and last, intersect with orthogonal sweep.

Approach

• optimization: instead of collecting, just look max and min on each line.

Complexity

• Time complexity: \(O(nlog(n))\), or O(n) for min-max

• Space complexity: \(O(n)\)

Code

// 463ms
    fun countCoveredBuildings(n: Int, b: Array<IntArray>) =
        listOf(b.indices.groupBy { b[it][0] }.values.map { it.sortedBy { b[it][1] }},
               b.indices.groupBy { b[it][1] }.values.map { it.sortedBy { b[it][0] }})
        .map { it.fold(HashSet<Int>()) { r, t -> r += t.drop(1).dropLast(1); r }}
        .reduce(Set<Int>::intersect).size

// 17ms
    pub fn count_covered_buildings(n: i32, b: Vec<Vec<i32>>) -> i32 {
        let (mut minY, mut maxY) = (vec![100000; n as usize+1], vec![0; n as usize+1]);
        let (mut minX, mut maxX) = (minY.clone(), maxY.clone());
        for b in &b { let (x,y) = (b[0] as usize, b[1] as usize);
            minY[x] = minY[x].min(y); maxY[x] = maxY[x].max(y);
            minX[y] = minX[y].min(x); maxX[y] = maxX[y].max(x);
        }
        b.iter().filter(|&b| { let (x,y) = (b[0] as usize, b[1] as usize);
            minX[y] < x && x < maxX[y] && minY[x] < y && y < maxY[x] }).count() as _
    }