NUHMAN.com

Introduction

LeetCode 305: Number of Islands II is a dynamic grid problem that asks us to count the number of islands on a 2D grid after a series of land additions. The key challenge here is to efficiently update the island count after each land addition, rather than recalculating the count from scratch every time. The problem uses a Union-Find (Disjoint Set Union) data structure to efficiently manage the connected components of the grid and maintain the island count.

Problem Statement

Given a 2D grid, initially filled with water (0), and a sequence of positions where land (1) is added to the grid, you are to return the number of islands after each land addition. An island is defined as a group of adjacent lands (horizontally or vertically). The number of islands can be computed dynamically after each land addition.

You must perform addLand(x, y) operations and compute the number of islands after each operation.

Example

python

# Example 1
Input:
["NumIslands2", "addLand", "addLand", "addLand", "addLand", "addLand"],
[[3, 3], [0, 0], [0, 1], [1, 1], [2, 2], [1, 0]]
Output:
[null, 1, 1, 2, 3, 3]

# Explanation:
# Initially, the grid is:
# 0 0 0 0
# 0 0 0 0
# 0 0 0 0
# 0 0 0 0
#
# After addLand(0, 0), the grid is:
# 1 0 0 0
# 0 0 0 0
# 0 0 0 0
# 0 0 0 0
# There is 1 island.
#
# After addLand(0, 1), the grid is:
# 1 1 0 0
# 0 0 0 0
# 0 0 0 0
# 0 0 0 0
# There is still 1 island.
#
# After addLand(1, 1), the grid is:
# 1 1 0 0
# 0 1 0 0
# 0 0 0 0
# 0 0 0 0
# Now, we have 2 islands.
#
# After addLand(2, 2), the grid is:
# 1 1 0 0
# 0 1 0 0
# 0 0 1 0
# 0 0 0 0
# Now, we have 3 islands.
#
# After addLand(1, 0), the grid is:
# 1 1 0 0
# 1 1 0 0
# 0 0 1 0
# 0 0 0 0
# There are still 3 islands.

✅ Step-by-Step Solution

🧠 Intuition

This problem can be tackled by keeping track of the number of connected components (islands) on the grid dynamically after each land addition. The Union-Find (Disjoint Set Union) data structure is well-suited for this problem because it can efficiently handle dynamic connectivity.

• Union-Find allows us to group the land cells into sets, and then merge these sets when new land is added that connects to an existing set.
• Each land addition may reduce the number of islands by merging two separate island groups. We need to efficiently update the number of islands after each land addition.

✅ Approach

1. Union-Find Data Structure:

• We will use a Union-Find (or Disjoint Set Union, DSU) structure with path compression and union by rank to efficiently manage the connected components (islands).
• Each cell in the grid can be represented as a unique number in a 1D array, and land additions are treated as union operations.
• Find: To check if two cells are part of the same island.
• Union: To merge two cells if they belong to different islands.

1. Grid to 1D Index Conversion:

• Since the Union-Find structure works with a 1D array, each cell in the 2D grid is converted to a unique index in the 1D array using the formula:

1. index=row×num_cols+col\text{index} = row \times \text{num\_cols} + colindex=row×num_cols+colThis ensures each cell is mapped to a unique index.
2. Dynamic Island Counting:

• For each land addition, we will check its neighbors (up, down, left, right).
• If a neighboring cell is also land, we will union the current cell with the neighboring cell, potentially reducing the number of islands.

1. Optimization:

• The Union-Find operations are efficient, with O(α(n)) time complexity per operation, where α is the inverse Ackermann function, which grows extremely slowly.
• This makes the solution scalable for large grids and multiple queries.

✅ Python Code

python

class NumIslands2:

    def __init__(self, m: int, n: int):
        self.m, self.n = m, n
        self.grid = [[0] * n for _ in range(m)]  # Initialize the grid
        self.parent = {}  # Map each cell to its parent in Union-Find
        self.rank = {}  # Store rank for union by rank
        self.island_count = 0  # To keep track of the number of islands
    
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    def union(self, x: int, y: int) -> bool:
        rootX = self.find(x)
        rootY = self.find(y)
        
        if rootX != rootY:
            # Union by rank
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            return True
        return False
    
    def addLand(self, row: int, col: int) -> int:
        if self.grid[row][col] == 1:
            return self.island_count
        
        # Mark the cell as land
        self.grid[row][col] = 1
        index = row * self.n + col
        self.parent[index] = index  # Initialize the parent
        self.rank[index] = 0  # Initialize the rank
        self.island_count += 1  # Increment the island count

        # Check four neighbors: up, down, left, right
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for dr, dc in directions:
            nr, nc = row + dr, col + dc
            if 0 <= nr < self.m and 0 <= nc < self.n and self.grid[nr][nc] == 1:
                neighbor_index = nr * self.n + nc
                if self.union(index, neighbor_index):
                    self.island_count -= 1  # If union happens, decrease island count
        
        return self.island_count

🧪 How It Works

1. Constructor:

• The NumIslands2 class is initialized with a grid of size m x n, and a 2D array grid representing the initial state of the grid (with water cells).
• We also initialize the parent and rank dictionaries to manage the Union-Find data structure, and a counter island_count to track the number of islands.

1. addLand Function:

• The addLand(row, col) function is called to add land at the specified position.
• If the position is already land, we simply return the current island count.
• Otherwise, we mark the cell as land, initialize its parent and rank, and increment the island count.
• Then, we check its four neighbors (up, down, left, right). For each valid neighbor, if it is land, we attempt to union the current cell with the neighbor, reducing the island count if they were separate islands.

1. Union-Find Operations:

• find(x): Returns the root of the island containing x, with path compression.
• union(x, y): Merges two islands if they are not already connected and updates the island count accordingly.

⏱️ Time and Space Complexity

MetricValueTime Complexity (addLand)O(α(n)) per operationSpace ComplexityO(m * n)

• Time Complexity (addLand): The time complexity per addLand operation is O(α(n)), where α is the inverse Ackermann function, which grows extremely slowly. For practical purposes, this is nearly constant time for typical inputs.
• Space Complexity: We need O(m * n) space to store the grid, the parent and rank dictionaries, where m is the number of rows and n is the number of columns in the grid.

🔍 Edge Cases

1. Initial Grid is Empty:

• If no land has been added yet, the island count is 0.

1. Multiple Additions at Same Location:

• If land is added to an already occupied position, no changes should occur, and the island count remains the same.

1. Grid Boundaries:

• Ensure that neighbors are only checked within the grid bounds.

✅ Conclusion

LeetCode 305: Number of Islands II is an advanced problem involving dynamic connectivity in a grid. By using the Union-Find data structure with path compression and union by rank, we can efficiently update the number of islands after each land addition. The solution leverages efficient O(α(n)) operations per land addition, making it scalable for large grids and multiple queries.