Number of Islands — DFS Flood Fill Interview Pattern (LC 200)

Problem Statement#

LeetCode 200 — Number of Islands (Medium). Given an m x n grid of '1' (land) and '0' (water), return the number of islands. An island is formed by connecting adjacent lands horizontally or vertically. All four edges are surrounded by water.

Constraints:

• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'
• Cells connect 4-directionally only

Input:  grid = [["1","1","0","0","0"],
                ["1","1","0","0","0"],
                ["0","0","1","0","0"],
                ["0","0","0","1","1"]]
Output: 3

Why This Problem Matters#

Number of Islands is the single most asked grid traversal problem in tech interviews. Keywords: "Number of Islands DFS", "LeetCode 200 BFS", "flood fill interview", "Amazon graph problem". If you can solve this cleanly in five minutes, you have proven you can implement DFS, handle bounds checking, and reason about connected components.

Every other grid problem (Max Area of Island, Surrounded Regions, Pacific Atlantic Water Flow) reuses this exact template.

The Core Insight#

Each '1' cell belongs to exactly one island. If you do a DFS or BFS starting at any land cell, you will visit every cell in that island and only that island. So the answer is the number of times you have to start a fresh DFS — once per unvisited land cell.

Visual Dry Run#

For the 4x5 example above, scanning row by row:

Solution (Optimal)#

class Solution:
    def numIslands(self, grid):
        if not grid or not grid[0]:
            return 0
        rows, cols = len(grid), len(grid[0])
        count = 0
 
        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return
            if grid[r][c] != '1':
                return
            grid[r][c] = '#'
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
 
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    count += 1
                    dfs(r, c)
        return count

var numIslands = function(grid) {
    if (!grid || grid.length === 0) return 0;
    const rows = grid.length, cols = grid[0].length;
    let count = 0;
 
    const dfs = (r, c) => {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        if (grid[r][c] !== '1') return;
        grid[r][c] = '#';
        dfs(r + 1, c);
        dfs(r - 1, c);
        dfs(r, c + 1);
        dfs(r, c - 1);
    };
 
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1') {
                count++;
                dfs(r, c);
            }
        }
    }
    return count;
};

BFS variant (avoids recursion depth issues)#

from collections import deque
 
def numIslands_bfs(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] = '#'
                while q:
                    cr, cc = q.popleft()
                    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                        nr, nc = cr+dr, cc+dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                            grid[nr][nc] = '#'
                            q.append((nr, nc))
    return count

Time: O(m * n) — each cell visited at most twice (once by the outer loop, once by DFS). Space: O(m * n) worst case for the recursion stack on a fully-land grid.

Common Mistakes#

• Forgetting to mark a cell visited before recursing, leading to infinite recursion.
• Using == instead of comparing the string '1' (LeetCode passes character grids, not int).
• Marking visited after popping in BFS, causing duplicate enqueues and TLE.
• Allocating a separate visited matrix when mutating the grid is allowed (wastes memory).
• Forgetting bounds check before reading grid[r][c].

Interview Tips#

• Ask whether the input grid can be mutated. If yes, mark in place; if no, use a visited set.
• State the time and space complexity before coding.
• Mention that BFS is preferred for very tall or wide grids to avoid recursion depth.
• Note that Union-Find is an alternative when islands can be added incrementally (LC 305).
• Walk through the example dry run on the whiteboard before writing code.

Follow-up Questions#

• Number of Islands II (LC 305) — islands appear one at a time. Hint: Union-Find.
• Max Area of Island (LC 695) — return the size of the largest island. Hint: DFS returns area.
• Count Sub-Islands (LC 1905) — count islands of grid2 fully inside grid1.
• What if diagonals count as adjacent? Add 4 more directions.
• Solve without recursion. Hint: explicit stack.

Key Takeaways#

• One DFS or BFS call per unvisited land cell equals one island.
• Mark visited the moment you enter a cell; never the moment you leave.
• Time is O(m * n), the size of the grid.
• DFS is shortest to write; BFS avoids recursion depth issues.
• Mutating the grid saves O(m * n) memory.
• This template solves Max Area, Sub-Islands, Surrounded Regions, and Pacific Atlantic.
• Union-Find is the right tool when land is added incrementally over time.