Strategies to Calculate Island Count in Dynamic Grids Using Python

Rate this post

πŸ’‘ Problem Formulation: The challenge involves creating a Python program that dynamically counts the number of islands in a grid as blocks (representative of land) are added one by one. An island is defined as a group of adjacent blocks not connected diagonally. The grids are initially empty and fill over time. The program needs to update and return the count of distinct islands after each addition. For example, starting with an empty 3×3 grid, adding blocks to coordinates (0,0), (0,1), and (1,0) respectively would result in a single island, thus the output after these additions would be 1.

Method 1: Union-Find Algorithm

The Union-Find (or Disjoint Set) algorithm is highly efficient for dynamic connectivity problems like island counting. It maintains a partition of elements into disjoint sets and supports two primary operations – find() to identify which set a particular element is in, and union() to merge two sets into one. This method excels in scenarios where the grid is frequently updated.

Here’s an example:

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]

    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):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot != yroot:
            self.parent[xroot] = yroot

def count_islands(grid):
    uf = UnionFind(len(grid) * len(grid[0]))
    island_count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                island_count += 1
                # Check adjacent blocks
                for dx, dy in [(-1, 0), (0, -1)]:
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] == 1:
                        if uf.find(nx * len(grid[0]) + ny) != uf.find(i * len(grid[0]) + j):
                            uf.union(nx * len(grid[0]) + ny, i * len(grid[0]) + j)
                            island_count -= 1
    return island_count

grid = [[0, 1, 0],
        [1, 0, 1],
        [0, 1, 0]]
print(count_islands(grid))

Output:

3

This code snippet creates a UnionFind class to manage disjoint sets. The count_islands function iterates through each grid cell, contributing to the island count when land is found. It reduces the island count when a new land block is connected to an existing island.

Method 2: Depth-First Search (DFS)

Depth-First Search is a classic graph traversal algorithm that can be adapted to count islands. Upon encountering a land block, the algorithm recursively explores adjacent land blocks, marking them as visited to avoid counting them as separate islands. This method works well for static grids but can be inefficient for dynamic ones.

Here’s an example:

def dfs(grid, i, j):
    if i = len(grid) or j = len(grid[0]) or grid[i][j] != 1:
        return
    grid[i][j] = '#'  # Mark as visited
    # Explore all adjacent blocks
    for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
        dfs(grid, i + dx, j + dy)

def count_islands(grid):
    island_count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                dfs(grid, i, j)
                island_count += 1
    return island_count

grid = [[0, 1, 0],
        [1, 0, 1],
        [0, 1, 0]]
print(count_islands(grid))

Output:

3

In this code snippet, the dfs function searches for and marks all connected land components, while the count_islands function iterates through the grid to initiate the DFS on unvisited land blocks. Each invocation of DFS corresponds to one island.

Method 3: Breadth-First Search (BFS)

Breadth-First Search algorithm functions similarly to DFS but explores all neighboring blocks first before moving to the next level of adjacent blocks. It’s appropriate to use where the grid is mostly water and islands are sparse and small. BFS may require additional memory for the queue, which can grow proportionally with the perimeter of the islands.

Here’s an example:

from collections import deque

def bfs(grid, i, j):
    queue = deque([(i, j)])
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    while queue:
        i, j = queue.popleft()
        for direction in directions:
            ni, nj = i + direction[0], j + direction[1]
            if 0 <= ni < len(grid) and 0 <= nj < len(grid[0]) and grid[ni][nj] == 1:
                grid[ni][nj] = '#'
                queue.append((ni, nj))

def count_islands(grid):
    island_count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                bfs(grid, i, j)
                island_count += 1
    return island_count

grid = [[0, 1, 0],
        [1, 0, 1],
        [0, 1, 0]]
print(count_islands(grid))

Output:

3

This example uses a deque to implement a BFS queue that traverses the grid level by level. The bfs function explores all direct neighbors of a block before moving on, effectively marking all parts of an island. The count_islands function calls bfs for each unvisited land block, treating each BFS exploration as a distinct island.

Method 4: Iterative Deepening Depth-First Search (IDDFS)

Iterative Deepening Depth-First Search combines the benefits of DFS with controlled exploration depth, improving upon space complexity. The method executes depth-limited DFS iterations with increasing depth, combining the thoroughness of DFS and the minimal memory usage of BFS.

Here’s an example:

def iddfs(grid, i, j, depth):
    # Base case: Maximum depth or out of bounds or water or visited
    if depth < 0 or i = len(grid) or j = len(grid[0]) or grid[i][j] != 1:
        return
    grid[i][j] = '#'  # Mark as visited
    for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
        iddfs(grid, i + dx, j + dy, depth - 1)

def count_islands(grid):
    max_depth = max(len(grid), len(grid[0]))
    island_count = 0
    for depth in range(max_depth):
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    iddfs(grid, i, j, depth)
                    island_count += 1
    return island_count

grid = [[0, 1, 0],
        [1, 0, 1],
        [0, 1, 0]]
print(count_islands(grid))

Output:

3

The code snippet shows how IDDFS operates by gradually increasing the search depth for each DFS iteration until it matches the larger dimension of the grid. The iddfs function performs the DFS with depth limitation, while the count_islands function iteratively applies IDDFS to find islands.

Bonus One-Liner Method 5: Recursive Set Update

This innovative one-liner approach leverages Python’s set comprehensions and recursion to calculate the island count. It constructs sets of adjacent blocks iteratively, using recursion to expand each set. This solution is elegant but may suffer from Python’s recursion limit on larger grids.

Here’s an example:

count_islands = lambda grid: sum(
    grid[i][j] and not any(grid[i][j] = grid[ni][nj] == 1 for ni, nj in [(i - 1, j), (i, j - 1)])
    for i in range(len(grid)) for j in range(len(grid[i]))
)

grid = [[0, 1, 0],
        [1, 0, 1],
        [0, 1, 0]]
print(count_islands(grid))

Output:

3

This one-liner redefines the island count as a sum of unique land blocks that cannot find an adjacent land block to the left or above it, essentially identifying the ‘top-left’ block of each island. This approach is concise but sacrifices readability and is subject to recursion depth limits.

Summary/Discussion

  • Method 1: Union-Find Algorithm. This method is highly efficient for dynamic and large grids. It offers near-constant time complexity for updates but requires understanding of disjoint set data structures.
  • Method 2: Depth-First Search. Classic and simple to understand. Ideal for static grids with a clear advantage in simplicity but may be inefficient for dynamic updates.
  • Method 3: Breadth-First Search. Good for small islands in large bodies of water. It tends to use more memory due to the queue but offers excellent performance on sparse grids.
  • Method 4: Iterative Deepening Depth-First Search. This approach melds DFS efficiency with controlled memory usage. Better for medium to larger grids where memory is a concern.
  • Bonus Method 5: Recursive Set Update. A terse and clever one-liner that shines in its brevity and suitability for very small grids. However, it is not suitable for large datasets and may challenge comprehensibility and recursion limits.