Number of Islands - Union Find Solution

#python #beginners #leetcode #computerscience

This is part of my series where I memo learning from Leetcode. If you have better solutions or ideas, please leave a comment!

Question

Number of Islands

We have to count the number of islands in Given a 2d grid map of '1's (land) and '0's (water).

An island is defined as below.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Approach

To check a 2d grid map, DFS or BFS is useful in many cases.

This question can be solved by DFS and Union Find Algorithm.
I'm gonna write about Union Find solution in this article.

In this algorithm, we can group the nodes and find the group number of some node(we can find the parent of some node).

To solve this question, if we find the '1'(land), we're gonna union the adjacent lands horizontally or vertically as much as possible.

Repeat the above process over and over again, and then finally the number of group is the answer for this question.

Solution

class Solution:

    def numIslands(self, grid: List[List[str]]) -> int:    
        if not grid:
            return 0
        grid_y = len(grid)
        grid_x = len(grid[0])

        uf = UnionFind(grid)

        for i in range(grid_y):
            for j in range(grid_x):
                if grid[i][j] == '1':
                    for k, l in ([1,0], [-1,0], [0,1], [0,-1]):
                        ny, nx = i+k, j+l
                        if 0<= ny < grid_y and 0 <= nx < grid_x and grid[ny][nx] == '1':
                            uf.union(i*grid_x+j, ny*grid_x+nx)
        return uf.count                     


class UnionFind:
    def __init__(self, grid):

        y = len(grid)
        x = len(grid[0])
        self.parents = [0] * (y*x)
        self.count = 0

        for i in range(y):
            for j in range(x):
                if grid[i][j] == '1':
                    self.parents[i*x+j] = -1
                    self.count += 1
    def find(self, x):

        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):

        x = self.find(x)
        y = self.find(y)

        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x,y = y,x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.count -= 1