← Back

🏝️ Graph - Number of Islands (DFS)

Find all connected components using DFS

👶Explain Like I'm 5

🏝️ Real-Life Example: Counting Islands from a Helicopter

You're flying over an ocean looking down at a grid map. Green squares 🟩 are land, blue squares 🟦 are water. An island is made of land squares that TOUCH each other (up, down, left, right - NOT diagonal corners).

🔍 Step 1: Scan the Map

Start at top-left, go row by row, checking every square like reading a book.

🏝️ Step 2: When You Find New Land

  1. Say "Found island #1!" and increment counter
  2. Paint it: Use DFS to explore and mark ALL connected land
  3. How DFS Works: From current land, explore up, down, left, right recursively until you hit water or already-painted land

🎨 Step 3: Keep Scanning

Continue scanning the grid. Already-painted land won't trigger a new island count. Each NEW unpainted land = new island!

💡 Key Insight: DFS explores deeply like following a trail in a maze - go as far as you can in one direction before backtracking. This ensures you find ALL connected land pieces in one island before moving to the next!

⚡ Why DFS? It naturally explores all connected components (islands) by exhaustively following each path until hitting a boundary (water)!

🔍 Code Debugger

ISLANDS: 0
1public int numIslands(char[][] grid) {
2int count = 0;
3...
4for (int r = 0; r < grid.length; r++) {
5for (int c = 0; c < grid[0].length; c++) {
6if (grid[r][c] == '1') {
7count++; // Found new island!
8dfs(grid, r, c); // Mark all connected land
9}
10}
11}
12return count;
13}
14...
15void dfs(char[][] grid, int r, int c) {
16if (r < 0 || c < 0 || r >= grid.length ||
17c >= grid[0].length || grid[r][c] == '0') return;
18grid[r][c] = '0'; // Mark as visited
19dfs(grid, r+1, c); dfs(grid, r-1, c);
20dfs(grid, r, c+1); dfs(grid, r, c-1);
21}

📊 Variables:

Island Count:0
row (r):0
col (c):0

🗺️ Island Grid

Land (Unvisited)
Water
Current Cell
Island (Visited)

Click "Start" to begin island detection

1.0x (1.5s per step)
🐌 0.3x (Very Slow)1.0x (Normal)🚀 2.0x (Fast)

☕ Complete Java Solution

DFS + Graph Pattern
public int numIslands(char[][] grid) {
    int count = 0;

    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == '1') {
                count++;  // Found new island!
                dfs(grid, r, c);  // Mark all connected land
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int r, int c) {
    // Base case: out of bounds or water
    if (r < 0 || c < 0 || r >= grid.length ||
        c >= grid[0].length || grid[r][c] == '0') {
        return;
    }

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

    // Explore all 4 directions
    dfs(grid, r + 1, c);  // Down
    dfs(grid, r - 1, c);  // Up
    dfs(grid, r, c + 1);  // Right
    dfs(grid, r, c - 1);  // Left
}

// Time: O(rows × cols), Space: O(rows × cols) for recursion

🎯 How Does This Algorithm Work?

1️⃣
Scan the entire grid row by row, cell by cell (nested for loops)
2️⃣
When you find unvisited land (char '1'): Increment island counter and start DFS
3️⃣
DFS marks all connected land: Recursively visit all 4 neighbors (up, down, left, right) until hitting water ('0') or grid boundary
4️⃣
Mark visited land as water: Change '1' to '0' to avoid revisiting (clever trick!)
5️⃣
Continue scanning: Already-visited land (now '0') won't trigger a new island count
💡
Time: O(m × n) - visit each cell at most twice. Space: O(m × n) for recursion stack in worst case (entire grid is one island)
🎯
Classic LeetCode Problems: #200 Number of Islands, #695 Max Area of Island, #733 Flood Fill, #547 Number of Provinces