Count Servers That Communicate

---

Intuition

• For each row, check if there is more than one computer. If there is, then count the number of computers in that row. If there is only one computer in that row, but there is more than one computer in the corresponding column, then still count that singleton computer since it is part of a network.

Complexity

Runtime

$O(MN)$

Space

$O(M+N)$

Code

Truncated

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        computers_r = defaultdict(list)
        computers_c = defaultdict(list)
 
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 1:
                    computers_r[r].append(c)
                    computers_c[c].append(r)
 
        res = 0
        for r in computers_r:
            if len(computers_r[r]) > 1 or (len(computers_r[r]) == 1 and len(computers_c[computers_r[r][0]]) > 1):
                res += len(computers_r[r])
 
        return res

Original

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        computers_r = defaultdict(list)
        computers_c = defaultdict(list)
 
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 1:
                    computers_r[r].append(c)
                    computers_c[c].append(r)
 
        res = 0
        for r in computers_r:
            if len(computers_r[r]) == 1:
                col = computers_r[r][0]
                if len(computers_c[col]) > 1:
                    res += len(computers_r[r])
            elif len(computers_r[r]) > 1:
                res += len(computers_r[r])
 
        return res

Notes

Cards

START Basic Front: Count Servers That Communicate Back: Check row for more than one, or if that same row has a column with more than one END

---

References

• Count Servers That Communicate