200. Number of Islands

This problem asks to count the number of islands in a given binary grid where '1' represents land and '0' represents water. Islands are connected horizontally or vertically.

We'll explore three common approaches: Depth-First Search (DFS), Breadth-First Search (BFS), and Union-Find.

Approach 1: Depth-First Search (DFS)

This approach recursively explores each connected landmass (island). When a '1' (land) is encountered, a DFS traversal marks all connected '1's as visited by changing them to '0', effectively sinking the island. The count of islands is incremented for each such traversal.

Algorithm:

1. Initialize ans to 0 (island count).
2. Iterate through each cell of the grid.
3. If a cell contains '1' (land):
   • Perform a DFS starting from that cell.
   • Increment ans.
4. Return ans.

The DFS function recursively explores the neighboring cells (up, down, left, right). If a neighbor is land ('1'), it's marked as visited ('0') and the DFS is recursively called on it.

Time Complexity: O(M*N), where M and N are the dimensions of the grid. Each cell is visited at most once.

Space Complexity: O(M*N) in the worst case (a single large island) due to the recursive call stack. Could be reduced to O(N) with iterative DFS.

Approach 2: Breadth-First Search (BFS)

Similar to DFS, BFS explores connected landmasses. However, instead of recursion, it uses a queue to manage cells to be visited.

Algorithm:

1. Initialize ans to 0.
2. Iterate through each cell.
3. If a cell is land ('1'):
   • Add it to the queue.
   • Mark it as visited ('0').
   • While the queue is not empty:
     • Dequeue a cell.
     • Explore its neighbors: if a neighbor is land ('1'), add it to the queue and mark it as visited.
   • Increment ans.
4. Return ans.

Time Complexity: O(M*N). Each cell is visited at most once.

Space Complexity: O(M*N) in the worst case (a single large island) due to the queue.

Approach 3: Union-Find

This approach uses a disjoint-set data structure (Union-Find) to efficiently group connected land cells.

Algorithm:

1. Initialize a parent array p of size M*N, where each element initially points to itself (representing individual islands).
2. Iterate through the grid.
3. For each land cell ('1'):
   • Find the root parent of its connected components (using find function).
   • Check its neighbors. If a neighbor is also land, union the components of both cells using union function.
4. Count the number of unique roots (islands).

The find function recursively finds the root of a component. The union function merges two components by setting the parent of one root to the other.

Time Complexity: Amortized O(MNα(M*N)), where α is the inverse Ackermann function (which grows extremely slowly, effectively constant for practical purposes).

Space Complexity: O(M*N) for the parent array.

Code Examples (Python)

DFS:

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    
    def dfs(row, col):
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == '0':
            return
        grid[row][col] = '0'  # Mark as visited
        dfs(row + 1, col)
        dfs(row - 1, col)
        dfs(row, col + 1)
        dfs(row, col - 1)
 
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count
 

BFS:

from collections import deque
 
def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                q = deque([(r, c)])
                grid[r][c] = '0'
                while q:
                    row, col = q.popleft()
                    for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                        nr, nc = row + dr, col + dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                            q.append((nr, nc))
                            grid[nr][nc] = '0'
    return count

Union-Find:

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    parent = list(range(rows * cols))
 
    def find(i):
        if parent[i] == i:
            return i
        parent[i] = find(parent[i])
        return parent[i]
 
    def union(i, j):
        root_i = find(i)
        root_j = find(j)
        if root_i != root_j:
            parent[root_i] = root_j
 
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                i = r * cols + c
                for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        j = nr * cols + nc
                        union(i, j)
 
    return sum(1 for i in range(rows * cols) if parent[i] == i and grid[i // cols][i % cols] == '1')

These examples demonstrate the three approaches. The choice of the best approach depends on the specific requirements and constraints of the problem. For most cases, DFS or BFS are simpler to implement, while Union-Find offers better performance for extremely large grids.