Problem statement

https://binarysearch.com/problems/Communication-Towers/

Solution

Create graph of connections, where for each tower find not more than 4 closest towers in each direction. Then perform dfs to find connected components.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, M):
        n, m = len(M), len(M[0])
        G = defaultdict(list)
        for i in range(n):
            row = [j for j in range(m) if M[i][j] == 1]
            for x, y in zip(row, row[1:]):
                G[(i, x)] += [(i, y)]
                G[(i, y)] += [(i, x)]
            for x in row:
                G[(i, x)] += [(i, x)]

        for j in range(m):
            col = [i for i in range(n) if M[i][j] == 1]
            for x, y in zip(col, col[1:]):
                G[(x, j)] += [(y, j)]
                G[(y, j)] += [(x, j)]

        V, idx = set(), 0

        def dfs(node, idx):
            V.add(node)
            for child in G[node]:
                if child not in V:
                    dfs(child, idx)

        for node in G.keys():
            if node not in V:
                dfs(node, idx)
                idx += 1

        return idx