AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Depth-First Search coding problems

Depth-first search follows one path as far as it goes before backing up: recursion over a tree, flood fill over a grid, connected components over a graph, and the explicit stack that replaces recursion when depth is a concern.

New to depth-first search? Read the Depth-First Search (DFS) tutorial first.

201 problems · 37 easy · 127 medium · 37 hard · judged by hidden tests in 13 languages

201problems

37 easy

127 medium

37 hard

Sign in to tick off what you solve.

Study plan: 14 problems · about 8 h 10 min

Start the study plan

Next up: Flood Fill

How it works

Depth-First Search, step by step

Depth-first search from A, with the call stack drawn out

edges = A–B, A–C, B–D, B–E, C–F, D–E; start = A

A#1BCDEFdfs(A)← topcall stackdiscovery order: A

Depth-first search follows one path as deep as it goes before trying another. dfs(A) is called: A is discovered 1st and pushed on the call stack.

0:01 / 0:38Step 1 of 12
Transcript · 12 steps

Study plan

Learn depth-first search in 8 days

14 of the 201 Depth-First Search problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 187 in the full list below are practice at your own pace. Then move on to Topological Sort.

  1. Day 1

    about 1 h 15 min

    Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

  2. Day 2

    about 55 min

    Medium problems: the same pattern with one twist each. Name the twist before you code.

  3. Day 3

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  4. Day 4

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  5. Day 5

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  6. Day 6

    about 50 min

    Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

  7. Day 7

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

  8. Day 8

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

    Next topic: Topological Sort

Depth-First Search Coding Problems: 201 Questions with Solutions

201 depth-first search coding problems — 37 easy · 127 medium · 37 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.

  • Problems: 201
  • By difficulty: 37 easy · 127 medium · 37 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

Depth-first search follows one path as far as it goes before backing up: recursion over a tree, flood fill over a grid, connected components over a graph, and the explicit stack that replaces recursion when depth is a concern. The problems here practise the visited bookkeeping, the base cases, and the choice between returning a value up the recursion and accumulating one in place.

New to depth-first search? Read the Depth-First Search (DFS) tutorial first.

How depth-first search works, step by step

A#1B#2C#5D#3E#4F#6emptycall stackdiscovery order: A B D E C F
Depth-first search from A, with the call stack drawn out. Example: edges = A–B, A–C, B–D, B–E, C–F, D–E; start = A
  1. Depth-first search follows one path as deep as it goes before trying another. dfs(A) is called: A is discovered 1st and pushed on the call stack.
  2. In dfs(A), B is unvisited, so dfs(B) is pushed on top and B is discovered 2nd. A's other neighbours wait until B's whole branch is finished.
  3. In dfs(B), D is unvisited, so dfs(D) is pushed on top and D is discovered 3rd. The stack always holds the path from A down to the node being explored.
  4. In dfs(D), E is unvisited, so dfs(E) is pushed on top and E is discovered 4th. The path is now A → B → D → E.
  5. E–B leads back to B, still on the stack: a back edge, which means the graph has a cycle, so it is not followed. Nothing unvisited is left around E: dfs(E) is popped and the search backtracks to D.
  6. Back in dfs(D), nothing unvisited is left: dfs(D) is popped and the search backtracks to B.
  7. Back in dfs(B), E is already finished (reached through D), so nothing unvisited is left: dfs(B) is popped and the search backtracks to A.
  8. Back in dfs(A), C is unvisited, so dfs(C) is pushed on top and C is discovered 5th. The search goes deep again from here.
  9. In dfs(C), F is unvisited, so dfs(F) is pushed on top and F is discovered 6th. That is every node found, but the open calls still have to return.
  10. F's only neighbour is C, its caller, so dfs(F) returns at once and the search backtracks to C.
  11. Back in dfs(C), nothing unvisited is left: dfs(C) is popped and the search backtracks to A.
  12. dfs(A) returns and the stack is empty. Discovery order: A, B, D, E, C, F; the teal edges are the calls made, the dashed one the back edge. Each node and edge is handled once: O(V + E).

Depth-First Search study plan

14 of the 201 Depth-First Search problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 187 in the full list below are practice at your own pace. Then move on to Topological Sort.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 6

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 8

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Topological Sort

Depth-First Search: the essentials

When to reach for it

Reachability, connected regions and properties of whole paths: count the islands, measure a region, decide whether a path exists, find a cycle in a directed graph. DFS does not give shortest paths in an unweighted graph, but it needs less bookkeeping than BFS, and its finishing order is what cycle detection and topological sorting rely on.

The pattern

Mark the node, then recurse into each unmarked neighbour. On a grid that may be modified, marking can mean overwriting the cell, land becoming water. Directed cycle detection needs three states, not two: unvisited, on the current path, and finished — reaching a node that is still on the current path closes a cycle.

def count_islands(grid):
    rows, cols = len(grid), len(grid[0])
    def sink(r, c):                 # 1 if (r, c) was unvisited land
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != 1:
            return 0
        grid[r][c] = 0              # mark before recursing
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            sink(r + dr, c + dc)
        return 1
    return sum(sink(r, c) for r in range(rows) for c in range(cols))

Cost

O(V + E) time. Space is the recursion depth, up to O(V) — a million frames on a 1000 × 1000 grid of land.

Common mistakes

  • Overflowing the call stack: Python stops at 1,000 frames by default, and other languages at whatever stack the process has. Use an explicit stack when depth can reach the input size.
  • Marking a node after the recursive calls instead of before, so two paths enter it.
  • One visited set for directed cycle detection, which mistakes a node finished on another branch for a cycle.
  • Forgetting to unmark when the question is about paths rather than reachability — that is Backtracking.

Start with

All depth-first search problems

Easy (37)

Medium (127)

Hard (37)

Companies that ask depth-first search problems

  • Amazon 186 problems on depth-first search
  • Google 135 problems on depth-first search
  • Microsoft 72 problems on depth-first search
  • Meta 50 problems on depth-first search
  • Bloomberg 13 problems on depth-first search
  • Samsung 7 problems on depth-first search
  • Adobe 6 problems on depth-first search
  • Flipkart 6 problems on depth-first search
  • LinkedIn 6 problems on depth-first search
  • LiveRamp 4 problems on depth-first search
  • Snapchat 4 problems on depth-first search
  • Uber 4 problems on depth-first search

Next topic: Topological Sort