Counting Islands

[!NOTE] This module explores the core principles of Connected Components, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

Problem: Given a graph (or grid), find the number of disconnected subgraphs. Common variant: Number of Islands (Grid of ‘1’s and ‘0’s).

Strategies:

1. DFS/BFS: Iterate through all nodes. If a node is unvisited, increment count and trigger traversal to mark all reachable nodes.
2. Union-Find: Initialize count = N. For every edge, union(u, v). If union succeeds, count--.

---

2. Interactive Analysis: Number of Islands

Click “Count” to start DFS. We scan row by row. When we find land (‘1’), we increment Islands and flood-fill to sink it (mark ‘0’).

Ready.

Islands Found: 0

---

3. Implementation

DFS (Number of Islands)

Java

Go

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                count++;
                dfs(grid, i, j);
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int r, int c) {
    if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '0') {
        return;
    }
    grid[r][c] = '0'; // Sink it
    dfs(grid, r + 1, c);
    dfs(grid, r - 1, c);
    dfs(grid, r, c + 1);
    dfs(grid, r, c - 1);
}

func numIslands(grid [][]byte) int {
    if len(grid) == 0 { return 0 }
    count := 0
    for r := 0; r < len(grid); r++ {
        for c := 0; c < len(grid[0]); c++ {
            if grid[r][c] == '1' {
                count++
                dfs(grid, r, c)
            }
        }
    }
    return count
}

func dfs(grid [][]byte, r, c int) {
    if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[0]) || grid[r][c] == '0' {
        return
    }
    grid[r][c] = '0'
    dfs(grid, r+1, c)
    dfs(grid, r-1, c)
    dfs(grid, r, c+1)
    dfs(grid, r, c-1)
}

---

4. Complexity Analysis

Strategy	Time	Space	Notes
DFS	O(M * N)	O(M * N)	Worst case recursion depth (all land).
BFS	O(M * N)	O(min(M, N))	Queue size bounded by diagonal.
Union-Find	O(M * N)	O(M * N)	Can be parallelized.