Today’s problem

https://leetcode.com/problems/count-servers-that-communicate/

Intuition

Do what the question ask.

Approach

First count the number of computers in each row and each column. Then count whether a computer has another computer that has the same row or column with it.

Complexity

  • Time complexity: $O(NM)$, N, M, are the length and the width of the grid.

  • Space complexity: $O(NM)$

Code

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        cntR = [0] * len(grid)
        cntC = [0] * len(grid[0])
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]:
                    cntR[i] += 1
                    cntC[j] += 1
        
        ans = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] and (cntR[i] > 1 or cntC[j] > 1):
                    ans += 1
        return ans