Count Servers that Communicate — LeetCode 1267 Python Solution

The problem

You are given a map of a server center, represented as a m * n integer matrix grid, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.

Example

Input

grid = [[1,0],[0,1]]

Output

0

Explanation

No servers can communicate with others.

Python solution

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        row = [0] * m
        col = [0] * n
        for i in range(m):
            for j in range(n):
                row[i] += grid[i][j]
                col[j] += grid[i][j]
        return sum(
            grid[i][j] and (row[i] > 1 or col[j] > 1)
            for i in range(m)
            for j in range(n)
        )

Complexity

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1267. Count Servers that Communicate is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Related problems