LeetCode 200: Number of Islands

link

The grid can be considered as an undirected graph where cells are the vertices and an edge (u, v) means both cells have "1" in them and they are neighbor of each other.

DFS

Each island is a connected component (cc) in the grid graph. So, we can count the cc’s in one DFS.

Time: $\mathcal{O}(m \cdot n)$ . If the entire grid is an island, the DFS will spiral towards the center, space: $\mathcal{O}(m \cdot n)$ .

from itertools import product as cartesian


class Solution:
    def dfs(self, r, c, grid):
        is_valid_row = lambda r: 0 <= r < len(grid)
        is_valid_col = lambda c: 0 <= c < len(grid[0])

        grid[r][c] = "*"
        for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            r2, c2 = r + dr, c + dc
            if not is_valid_row(r2) or not is_valid_col(c2):
                continue
            if grid[r2][c2] != "1":
                continue

            self.dfs(r2, c2, grid)

    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])

        island_count = 0
        for r, c in cartesian(range(m), range(n)):
            if grid[r][c] == "1":
                island_count += 1
                self.dfs(r, c, grid)

        return island_count

BFS

Time: $\mathcal{O}(m \cdot n)$ , space: $\mathcal{O}(m + n)$ .

from itertools import product as cartesian

class Solution:

    def bfs(self, u, grid):
        is_valid_row = lambda r: 0 <= r < len(grid)
        is_valid_col = lambda c: 0 <= c < len(grid[0])

        q = deque([u])
        while q:
            r, c = q.popleft()
            grid[r][c] = "*"
            for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                r2, c2 = r+dr, c+dc
                if not is_valid_row(r2) or not is_valid_col(c2):
                    continue
                if grid[r2][c2] != "1":
                    continue
                
                q.append( (r2, c2) )
            

    def numIslands(self, grid: List[List[str]]) -> int:
        island_count = 0
        m, n = len(grid), len(grid[0])
        for r, c in cartesian(range(m), range(n)):
            if grid[r][c] != "1":
                continue
                
            island_count += 1
            self.bfs((r, c), grid)

        return island_count

Union-find

We start with the count of 1-cell’s number of connected components. For each 1-cell, we add at most four edges. If two of these cells were not previously connected, the number of connected components reduces by one.

Time: $\mathcal{O}(m \cdot n \cdot \lg^*{(m \cdot n)})$ , space: $\mathcal{O}(m \cdot n)$ .

from itertools import product as cartesian


class UnionFind:
    def __init__(self, grid):
        m, n = len(grid), len(grid[0])
        self.parent_of, self.rank_of = {}, {}
        self.component_count = 0
        for r, c in cartesian(range(m), range(n)):
            if grid[r][c] != "1":
                continue

            self.parent_of[(r, c)] = (r, c)
            self.rank_of[(r, c)] = 0
            self.component_count += 1

    def __compress_path(self, u, root):
        while u != (p := self.parent_of[u]):
            self.parent_of[u] = root
            u = p

    def __find(self, u):
        root = u
        while root != (p := self.parent_of[root]):
            root = p
        self.__compress_path(u, root)

        return root

    def connect(self, u, v):
        root_u = self.__find(u)
        root_v = self.__find(v)
        if root_u == root_v:
            return

        self.component_count -= 1

        rank_u = self.rank_of[u]
        rank_v = self.rank_of[v]
        if rank_u == rank_v:
            self.parent_of[root_u] = root_v
            self.rank_of[root_v] += 1
            return

        if rank_u > rank_v:
            self.parent_of[root_v] = root_u
        else:
            self.parent_of[root_u] = root_v


class Solution:
    def get_edges(self, r, c, grid):
        if grid[r][c] != "1":
            return []

        is_valid_row = lambda r: 0 <= r < len(grid)
        is_valid_col = lambda c: 0 <= c < len(grid[0])

        edges = []
        for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            r2, c2 = r + dr, c + dc
            if not is_valid_row(r2) or not is_valid_col(c2):
                continue
            if grid[r2][c2] != "1":
                continue

            edges.append([(r, c), (r2, c2)])

        return edges

    def numIslands(self, grid: List[List[str]]) -> int:
        uf = UnionFind(grid)
        m, n = len(grid), len(grid[0])
        for r, c in cartesian(range(m), range(n)):
            for e in self.get_edges(r, c, grid):
                u, v = e
                uf.connect(u, v)

        return uf.component_count

unreasonably effective