Skip to content
Companies
    
DSA Patterns

Learn

Depth First Search (DFS)

DFS explained: the recursive template, flood fill on grids, the four-direction sweep, visited-set placement, and when to reverse the problem instead.

3 min readUpdated 2 Sept 2026

#Graphs#Grids#Recursion#Flood Fill

DFS is the default traversal: it is shorter than BFS, uses less memory on deep-and-narrow structures, and the recursion usually mirrors the problem's own shape. Reach for it whenever the question is about whether things are connected, or about exploring everything, rather than about the shortest route.

The idea

Go as deep as possible along one path, then back up and try the next. Recursion gives you the backing-up for free — the call stack is the path you took to get here.

def dfs(node, seen):
    if node in seen:
        return
    seen.add(node)
    for nxt in neighbours(node):
        dfs(nxt, seen)

On a grid, "neighbours" is the four-direction sweep, and the bounds check doubles as the base case:

DIRECTIONS = ((1, 0), (-1, 0), (0, 1), (0, -1))

def flood(grid, r, c):
    if not (0 <= r < len(grid) and 0 <= c < len(grid[0])):
        return                      # off the board
    if grid[r][c] != 1:
        return                      # water, or already visited
    grid[r][c] = 0                  # mark, in place
    for dr, dc in DIRECTIONS:
        flood(grid, r + dr, c + dc)

Pushing the bounds and validity checks into the top of the function rather than guarding before each recursive call is what keeps grid DFS short. Write it the other way and the call site grows four compound conditions.

Counting components

Number of Islands is the pattern's canonical form: sweep the grid, and every time you land on unvisited land, that is one new component — flood it so it is never counted again.

def num_islands(grid):
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == 1:
                flood(grid, r, c)
                count += 1
    return count

The same skeleton answers Max Area of Island (return a size from the recursion instead of counting), Number of Connected Components (the graph version), and Clone Graph (carry a old → new map and return the copy).

Reversing the problem

Surrounded Regions and Pacific Atlantic Water Flow are the two that teach the most

useful idea in this pattern: **when the condition is hard to check going forwards, start from the exceptions instead.**

Surrounded Regions asks you to flip every region not touching the border. Testing each region for border-contact is fiddly; flooding inward from the border marks exactly the survivors, and everything left unmarked is by definition surrounded.

Pacific Atlantic asks which cells drain to both oceans. Simulating drainage from each cell is O((mn)²). Instead run DFS uphill from each ocean's edge — inverting the flow condition — and intersect the two reachable sets. One pass each.

def pacific_atlantic(heights):
    rows, cols = len(heights), len(heights[0])
    pacific, atlantic = set(), set()

    def climb(r, c, seen, prev):
        if (r, c) in seen or not (0 <= r < rows and 0 <= c < cols):
            return
        if heights[r][c] < prev:            # water cannot flow uphill into here
            return
        seen.add((r, c))
        for dr, dc in DIRECTIONS:
            climb(r + dr, c + dc, seen, heights[r][c])

    for c in range(cols):
        climb(0, c, pacific, 0)
        climb(rows - 1, c, atlantic, 0)
    for r in range(rows):
        climb(r, 0, pacific, 0)
        climb(r, cols - 1, atlantic, 0)

    return [list(cell) for cell in pacific & atlantic]

DFS with undo: Word Search

When a cell may be reused by a different path, marking is not permanent — you mark on the way in and unmark on the way out. That is backtracking, and Word Search is the crossover problem:

def exist(board, word):
    def search(r, c, i):
        if i == len(word):
            return True
        if not (0 <= r < len(board) and 0 <= c < len(board[0])):
            return False
        if board[r][c] != word[i]:
            return False

        board[r][c] = "#"                       # mark for THIS path only
        found = any(search(r + dr, c + dc, i + 1) for dr, dc in DIRECTIONS)
        board[r][c] = word[i]                   # undo
        return found

    return any(
        search(r, c, 0) for r in range(len(board)) for c in range(len(board[0]))
    )

Getting this distinction right is most of what separates the DFS questions from each other: connectivity marks permanently, path search marks and undoes.

Complexity

O(V + E) — on a grid, O(rows × cols), since each cell is visited a constant number of times. Space is O(V) worst case for the recursion stack, which on a full grid means the stack can reach rows × cols deep. On very large grids that is a real stack-overflow risk, and converting to an explicit stack is the fix worth naming.

Mistakes that cost the round

  • Marking permanently in a path-search problem (or forgetting to undo), which makes

valid answers unreachable.

  • Using DFS for a shortest path. It finds a path, not the shortest one.
  • Recursing without a visited set on a cyclic graph — infinite recursion. Trees are

the exception, which is why tree DFS looks deceptively simple.

  • Checking bounds at the call site in four separate conditions instead of at the top

of the function.

  • Ignoring stack depth on grids the size of the constraints.

What to drill

  1. Number of Islands — count components by flooding.
  2. Clone Graph — DFS carrying a map.
  3. Surrounded Regions — flood from the border instead.
  4. Pacific Atlantic Water Flow — invert the condition, intersect two sweeps.
  5. Word Search — mark and undo.

All on the 22 DSA Patterns sheet.

Frequently asked

What is the difference between DFS and BFS?

DFS goes as deep as it can before backtracking, using a stack (usually the call stack); BFS expands level by level using a queue. BFS finds shortest paths on unweighted graphs and DFS does not, but DFS uses O(depth) space rather than O(width) and is usually shorter to write for connectivity and exhaustive-exploration problems.

Should I mark a cell visited permanently in DFS?

Permanently when you are measuring connectivity — islands, components, regions — because each cell belongs to exactly one answer. Mark and then undo when you are searching for a path, as in Word Search, because a cell blocked for the current path must be available to a different one.

Can DFS cause a stack overflow?

Yes. On a grid where every cell is connected, the recursion can reach rows × cols deep, which exceeds the default stack limit in many languages at typical LeetCode constraint sizes. Converting the recursion to an explicit stack is the standard fix and a good thing to mention unprompted.

Related

Backtracking

Choose, recurse, un-choose. One template generates every subset, permutation and combination — pruning is what makes it fast.

Breadth First Search (BFS)

A queue, a visited set, and level-by-level expansion — the shortest path on any unweighted graph.

Dynamic Programming

Define the state, write the recurrence, memoise, then tabulate. Five families cover almost every DP question asked.