LC-1267 Medium LeetCode

1267. Count Servers that Communicate

Array Depth-First Search Breadth-First Search Union Find Matrix Counting

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 73% Topics: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix, Counting

View full problem on LeetCode

Reading material

Arrays & Hashing 12 min Trees & Traversals 18 min Union–Find (DSU) 12 min

Reference solution (spoiler · python)

# Time:  O(m * n)
# Space: O(m + n)

class Solution(object):
    def countServers(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        rows, cols = [0]*len(grid), [0]*len(grid[0])
        for i in xrange(len(grid)):
            for j in xrange(len(grid[0])):
                if grid[i][j]:
                    rows[i] += 1
                    cols[j] += 1
        result = 0
        for i in xrange(len(grid)):
            for j in xrange(len(grid[0])):
                if grid[i][j] and (rows[i] > 1 or cols[j] > 1):
                    result += 1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT