LeetCode Entry

1267. Count Servers that Communicate

23.01.2025 medium 2025 kotlin rust

Connected servers by row or column

1267. Count Servers that Communicate medium blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/873

Problem TLDR

Connected servers by row or column #medium

Intuition

The brute force is accepted.

Some optimizations: we can count rows and columns frequency, then scan servers with any freq > 1.

Another way is to us Union-Find.

Approach

  • let’s golf in Kotlin

Complexity

  • Time complexity: \(O(nm)\)

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

Code


    fun countServers(g: Array<IntArray>) = g
        .flatMap { r -> r.indices.map { r to it }}
        .count { (r, x) -> r[x] * g.sumOf { it[x] } * r.sum() > 1 }



    pub fn count_servers(grid: Vec<Vec<i32>>) -> i32 {
        let (mut rs, mut cs, mut vs) =
          (vec![0; grid.len()], vec![0; grid[0].len()], vec![]);
        for y in 0..grid.len() { for x in 0..grid[0].len() {
            if grid[y][x] > 0 { rs[y] += 1; cs[x] += 1; vs.push((y, x)) }
        }}
        vs.into_iter().filter(|&(y, x)| rs[y] > 1 || cs[x] > 1).count() as i32
    }



    int countServers(vector<vector<int>>& g) {
        int r[250], c[250]; int s = 0;
        for (int y = 0; y < size(g); ++y)
            for (int x = 0; x < size(g[0]); ++x)
                g[y][x] && (++r[y], ++c[x]);
        for (int y = 0; y < size(g); ++y)
            for (int x = 0; x < size(g[0]); ++x)
                s += g[y][x] * r[y] * c[x] > 1;
        return s;
    }