Connected Components

[!NOTE] If the world is a graph, continents are connected components. Your job is to count them.

1. The Problem: Counting Islands

Given a grid of 1s (Land) and 0s (Water), count the number of distinct islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

  • Input: A Grid or Adjacency List.
  • Output: An Integer (Count).
  • Method: Iterate through every node. If it’s unvisited land, increment count and trigger a traversal (DFS/BFS) to mark the entire island as visited.

2. Interactive: Island Finder

Click to toggle Land/Water. The algorithm automatically counts the islands and colors them distinctly.

Islands Found: 0

3. Code Implementation: Number of Islands

public int numIslands(char[][] grid) {
  if (grid == null || grid.length == 0) return 0;

  int count = 0;
  int rows = grid.length;
  int cols = grid[0].length;

  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      if (grid[i][j] == '1') {
        count++;
        dfs(grid, i, j);
      }
    }
  }
  return count;
}

private void dfs(char[][] grid, int r, int c) {
  int rows = grid.length;
  int cols = grid[0].length;

  if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') {
    return;
  }

  grid[r][c] = '0'; // Mark as visited (sink the island)

  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
  rows := len(grid)
  cols := len(grid[0])

  for r := 0; r < rows; r++ {
    for c := 0; c < cols; 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' // Sink

  dfs(grid, r+1, c)
  dfs(grid, r-1, c)
  dfs(grid, r, c+1)
  dfs(grid, r, c-1)
}

4. Deep Dive Strategy Lab: Connected Components

Intuition Through Analogy

Think of this chapter like city route planning. The goal is not to memorize a fixed trick, but to repeatedly answer:

  1. What is the bottleneck?
  2. Which constraint dominates (time, memory, latency, correctness)?
  3. Which representation makes the bottleneck easier to eliminate?

5. Complexity Analysis

Approach Time Complexity Space Complexity Description
DFS/BFS O(R * C) O(R * C) We visit each cell at most once. In the worst case (all land), the recursion stack (or queue) can grow to R * C.