Depth-First Search (DFS)

Intuition

Think of the paint bucket tool in an image editor. You click one pixel, and the colour spreads to every touching pixel of the same colour, then to their touching pixels, until the region is filled. The tool does not care about distance; it only cares about connectivity. That is the job grid DFS does best: given one cell, find everything connected to it.

Counting islands builds on that. Scan the grid cell by cell. Whenever you land on unvisited land, you have found a new island; run DFS from that cell to sink the whole island so later scans do not count it again. The number of times you start a DFS is the answer, exactly like counting connected components in Graph DFS.

How it works step by step

1. Loop over every cell (r, c) in row-major order.
2. If the cell is land ('1') and not yet visited, increment the island counter and call sink(r, c).
3. Inside sink: return immediately if the cell is out of bounds, water, or already visited. This base case at the top keeps the neighbor code simple.
4. Mark the cell visited, for example by overwriting it with '0'.
5. Recurse into the four neighbors: up, down, left, right.
6. When the outer loop finishes, the counter holds the number of islands. For flood fill, skip the counter and replace the colour while marking.

Dry run: counting islands

Grid rows are 1 1 0, 0 1 0, 1 0 1. Visited land is sunk to 0. The stack column shows the pending recursive calls on land cells.

The answer is 3. Note that (2,0) and (1,1) touch only diagonally, so with 4-direction connectivity they are separate islands. If the problem counted diagonals, (2,0), (1,1) and (2,2) would merge and the answer would be 1.

Code

public class NumberOfIslands {
    public int numIslands(char[][] grid) {
        int islands = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == '1') {
                    islands++;
                    sink(grid, r, c);
                }
            }
        }
        return islands;
    }

    private void sink(char[][] grid, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return;
        if (grid[r][c] != '1') return;       // water or already visited
        grid[r][c] = '0';                    // mark before recursing
        sink(grid, r - 1, c);
        sink(grid, r + 1, c);
        sink(grid, r, c - 1);
        sink(grid, r, c + 1);
    }
}

def flood_fill(image, sr, sc, color):
    """Iterative DFS flood fill (LeetCode 733); safe on very large regions."""
    original = image[sr][sc]
    if original == color:          # nothing to do, and avoids an infinite loop
        return image
    rows, cols = len(image), len(image[0])
    stack = [(sr, sc)]
    image[sr][sc] = color
    while stack:
        r, c = stack.pop()
        for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original:
                image[nr][nc] = color      # recolouring doubles as the visited mark
                stack.append((nr, nc))
    return image


def max_area_of_island(grid):
    """Same stack-based DFS, returning the size of the largest island."""
    rows, cols, best = len(grid), len(grid[0]), 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1:
                continue
            grid[r][c], stack, area = 0, [(r, c)], 0
            while stack:
                cr, cc = stack.pop()
                area += 1
                for nr, nc in ((cr - 1, cc), (cr + 1, cc), (cr, cc - 1), (cr, cc + 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        grid[nr][nc] = 0
                        stack.append((nr, nc))
            best = max(best, area)
    return best


print(flood_fill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2))  # [[2,2,2],[2,2,0],[2,0,1]]
print(max_area_of_island([[1, 1, 0], [0, 1, 0], [1, 0, 1]]))   # 3

Time and space complexity

The worst case is real. A 1000 x 1000 grid of all land can drive recursion a million frames deep. Java's default thread stack usually fails long before that, and CPython stops at about 1000 frames unless you raise sys.setrecursionlimit, which only moves the crash to the C stack. The explicit stack in the Python code lives on the heap and has no such limit.

Edge cases

• Empty grid or zero columns: guard grid[0] before reading its length.
• All water: the outer loop finishes with 0 islands and never recurses.
• All land: one island, and the deepest possible recursion; this is the test that exposes stack overflows.
• Flood fill with the same colour: if the new colour equals the old one, return early or the marking never distinguishes visited cells.
• Islands touching the border: problems like Surrounded Regions or Number of Enclaves treat them differently, so start DFS from the border first.

Common mistakes

• Marking a cell after the recursive calls instead of before. Two neighbors then recurse into each other forever.
• Comparing the char grid with the integer 1 in Java, or the int grid with the string '1' in Python. LeetCode #200 uses characters.
• Using DFS to answer a shortest-path question. It finds a path quickly, but not the shortest.
• Writing four nearly identical bounds checks in four places instead of one check at the top of the function.
• Counting diagonal neighbors when the problem defines adjacency as horizontal and vertical only, or the reverse.

Variations: why DFS paths are not shortest

On an open 3 x 3 grid from the top-left to the top-right corner, a DFS that tries down and up before left and right will plunge to the bottom of the first column and then zigzag back up, a path of 6 moves when 2 would do. DFS commits to the first direction that works and only backtracks at a dead end, so the first route it finds depends on direction order, not length. Finding the true minimum with DFS means exploring every path, which is exponential. That is why reachability, region size, perimeter and connectivity belong to DFS, while minimum moves belong to BFS on a grid. Backtracking problems such as Word Search are DFS that un-marks a cell on the way back out so it can be used by another path.

Related LeetCode problems

• #200 Number of Islands — the lesson's main pattern: count how many times the scan starts a DFS.
• #733 Flood Fill — DFS recolours one connected region in place.
• #695 Max Area of Island — DFS returns the size of each island and you keep the maximum.
• #130 Surrounded Regions — DFS from border O cells marks the ones that must survive.
• #417 Pacific Atlantic Water Flow — run DFS uphill from each ocean's border and intersect the results.
• #1020 Number of Enclaves — sink border-connected land first, then count what is left.
• #79 Word Search — backtracking DFS that unmarks cells when it returns.

FAQ