Number of Islands (Disjoint Set Union - DSU)

Welcome to a deep dive into the fascinating world of Data Structures and Algorithms! Today, we'll learn about the Number of Islands problem, a classic algorithmic challenge that's essential for any aspiring developer.

What are Islands? 🎯

In the context of this problem, an island is a group of connected 1s (land) surrounded by 0s (water) in a 2D grid. The main goal is to count the total number of these islands. Let's visualize this:

In this example, there are three islands: the first one (top left), the second one (middle), and the third one (bottom right).

Disjoint Set Union (DSU) 📝

To solve the Number of Islands problem, we'll be using a powerful data structure called Disjoint Set Union (DSU). It allows us to efficiently handle the connections between the elements (islands) in our 2D grid.

Let's create a simple DSU implementation for our problem:

python

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return
        if self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
            self.rank[rootX] += self.rank[rootY]
        else:
            self.parent[rootX] = rootY
            self.rank[rootY] += self.rank[rootX]

    def count(self):
        return len(set(self.parent))

Now, let's solve the Number of Islands problem using our DSU implementation:

python

def num_islands(grid):
    if not grid:
        return 0

    rows = len(grid)
    cols = len(grid[0])
    dsu = DSU(rows * cols)

    def dfs(r, c):
        if r < 0 or r == rows or c < 0 or c == cols or grid[r][c] == 0:
            return
        grid[r][c] = 0
        dsu.union((r * cols) + c, (r - 1) * cols + c)
        dsu.union((r * cols) + c, (r + 1) * cols + c)
        dsu.union((r * cols) + c, r * cols + c - 1)
        dsu.union((r * cols) + c, r * cols + c + 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                dfs(r, c)

    return dsu.count()

Putting It All Together ✅

Now that we have our DSU implementation and the Number of Islands solution, let's try some examples:

python

grid1 = [
    [1, 1, 0, 0, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 1, 1]
]

grid2 = [
    [1],
    [1],
    [1],
    [1],
    [1]
]

print(num_islands(grid1))  # Output: 3
print(num_islands(grid2))  # Output: 1

Number of Islands (Disjoint Set Union - DSU)

Number of Islands (Disjoint Set Union - DSU)

What are Islands? 🎯

Disjoint Set Union (DSU) 📝

Putting It All Together ✅

Quiz 💡