Count Servers that Communicate

Problem Id: 1267 Difficulty: Medium Tag: Array Tag: Graph


Intuition

When I first see this problem, I thought I need to use some graph algorithm to solve this problem, like DFS or BFS. Soon I realized that this problem is to calculate the indegree of each vertex and return the count of vertices whose indegree are greater than 2.

Solution


class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        row_count = [0] * rows
        col_count = [0] * cols

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    row_count[i] += 1
                    col_count[j] += 1

        count = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    if row_count[i] > 1 or col_count[j] > 1:
                        count += 1
        return count