Autocoder

DFS (Depth-First Search) Interview Questions

Last updated 2026-11-19

Depth-first search follows one path as far as it can before backing up. It is the natural tool for counting components, exploring grids, backtracking and any problem that asks about the structure of paths. A recursive DFS is only a few lines, which is why interviewers use it to test care with boundaries and visited state.

These problems are ordered from easy to hard and include Python and Java code, complexity and edge cases. For graph modelling see graph interview questions, and for fewest-steps problems see BFS interview questions.

Data structureRecursion or explicit stack
CostO(V + E), or O(R * C) on a grid
Best forComponents, cycles, backtracking, path existence
RiskRecursion depth on large inputs

The pattern and when to spot it

Use DFS when the question is about whether something is reachable, how big a connected region is, or how many regions exist. On a grid, the template is: check bounds and visited, mark the cell, recurse into four neighbours. Marking by overwriting the cell removes the need for a separate visited array but changes the input, so say so.

Two refinements matter. For backtracking, such as word search, unmark the cell when you return so other paths can use it. For path-length questions on a DAG or a strictly increasing grid, add memoisation, because the same sub-result is reached repeatedly. Searching backwards from the border or the target often beats testing every cell, as in surrounded regions and Pacific Atlantic.

Common mistakes

DFS (Depth-First Search) Interview Questions: questions with worked answers

  1. 1

    Flood fill

    easy

    Remember the original colour of the start pixel, then DFS to every 4-connected pixel with that colour and repaint it. If the new colour equals the old one, return immediately; otherwise the repaint never marks a pixel as done and the recursion never ends. Time O(R * C), space O(R * C) recursion in the worst case. Edge cases: new colour equal to old colour, a single pixel image, start pixel on the border.

    python
    def flood_fill(img, sr, sc, color):
        old = img[sr][sc]
        if old == color:
            return img
        def dfs(r, c):
            if not (0 <= r < len(img) and 0 <= c < len(img[0])) or img[r][c] != old:
                return
            img[r][c] = color
            dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)
        dfs(sr, sc)
        return img
    java
    int[][] floodFill(int[][] img, int sr, int sc, int color) {
        int old = img[sr][sc];
        if (old != color) dfs(img, sr, sc, old, color);
        return img;
    }
    private void dfs(int[][] img, int r, int c, int old, int color) {
        if (r < 0 || c < 0 || r >= img.length || c >= img[0].length || img[r][c] != old) return;
        img[r][c] = color;
        dfs(img, r + 1, c, old, color); dfs(img, r - 1, c, old, color);
        dfs(img, r, c + 1, old, color); dfs(img, r, c - 1, old, color);
    }
  2. 2

    Number of islands

    medium

    Scan the grid. At each land cell not yet visited, count one island and DFS to sink all connected land by overwriting it with water. Each cell is visited a constant number of times. Time O(R * C), space O(R * C) recursion worst case. Edge cases: empty grid, all water, all land (one island), diagonal cells are not connected, input of characters vs integers.

    python
    def num_islands(grid):
        R, C, count = len(grid), len(grid[0]), 0
        def sink(r, c):
            if 0 <= r < R and 0 <= c < C and grid[r][c] == '1':
                grid[r][c] = '0'
                sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1)
        for r in range(R):
            for c in range(C):
                if grid[r][c] == '1':
                    count += 1
                    sink(r, c)
        return count
    java
    int numIslands(char[][] g) {
        int count = 0;
        for (int r = 0; r < g.length; r++)
            for (int c = 0; c < g[0].length; c++)
                if (g[r][c] == '1') { count++; sink(g, r, c); }
        return count;
    }
    private void sink(char[][] g, int r, int c) {
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
        g[r][c] = '0';
        sink(g, r + 1, c); sink(g, r - 1, c); sink(g, r, c + 1); sink(g, r, c - 1);
    }
  3. 3

    Maximum area of an island

    medium

    Same traversal as counting islands, but the DFS returns the number of cells it sinks: 1 plus the results of the four neighbours. Keep the largest return value over all starting cells. Time O(R * C), space O(R * C) recursion worst case. Edge cases: no land (0), a single huge island that causes deep recursion, islands touching the border.

    python
    def max_area(grid):
        R, C = len(grid), len(grid[0])
        def dfs(r, c):
            if not (0 <= r < R and 0 <= c < C) or grid[r][c] != 1:
                return 0
            grid[r][c] = 0
            return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
        return max(dfs(r, c) for r in range(R) for c in range(C))
    java
    int maxArea(int[][] g) {
        int best = 0;
        for (int r = 0; r < g.length; r++)
            for (int c = 0; c < g[0].length; c++) best = Math.max(best, dfs(g, r, c));
        return best;
    }
    private int dfs(int[][] g, int r, int c) {
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != 1) return 0;
        g[r][c] = 0;
        return 1 + dfs(g, r + 1, c) + dfs(g, r - 1, c) + dfs(g, r, c + 1) + dfs(g, r, c - 1);
    }
  4. 4

    Number of provinces from an adjacency matrix

    medium

    isConnected[i][j] = 1 means cities i and j are directly linked. A province is a connected component. DFS from each unvisited city over its row, and count how many searches you start. Time O(n^2), space O(n). Edge cases: a matrix with only the diagonal set (n provinces), a fully connected matrix (1), symmetric input assumed.

    python
    def find_circle_num(m):
        n, seen, count = len(m), set(), 0
        def dfs(i):
            for j in range(n):
                if m[i][j] and j not in seen:
                    seen.add(j)
                    dfs(j)
        for i in range(n):
            if i not in seen:
                seen.add(i)
                dfs(i)
                count += 1
        return count
    java
    int findCircleNum(int[][] m) {
        boolean[] seen = new boolean[m.length];
        int count = 0;
        for (int i = 0; i < m.length; i++)
            if (!seen[i]) { dfs(m, i, seen); count++; }
        return count;
    }
    private void dfs(int[][] m, int i, boolean[] seen) {
        seen[i] = true;
        for (int j = 0; j < m.length; j++)
            if (m[i][j] == 1 && !seen[j]) dfs(m, j, seen);
    }
  5. 5

    Surrounded regions: capture O regions not touching the border

    medium

    Work backwards. Any O connected to the border cannot be captured. DFS from every border O and mark those cells with a temporary symbol, then flip all remaining O to X and restore the temporary symbol to O. Time O(R * C), space O(R * C). Edge cases: a board with no interior, regions touching the border at a single cell, grids with one row or column.

    python
    def solve(board):
        R, C = len(board), len(board[0])
        def mark(r, c):
            if 0 <= r < R and 0 <= c < C and board[r][c] == 'O':
                board[r][c] = 'S'
                mark(r + 1, c); mark(r - 1, c); mark(r, c + 1); mark(r, c - 1)
        for r in range(R):
            mark(r, 0); mark(r, C - 1)
        for c in range(C):
            mark(0, c); mark(R - 1, c)
        for r in range(R):
            for c in range(C):
                board[r][c] = 'O' if board[r][c] == 'S' else 'X'
    java
    void solve(char[][] b) {
        int R = b.length, C = b[0].length;
        for (int r = 0; r < R; r++) { mark(b, r, 0); mark(b, r, C - 1); }
        for (int c = 0; c < C; c++) { mark(b, 0, c); mark(b, R - 1, c); }
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++) b[r][c] = b[r][c] == 'S' ? 'O' : 'X';
    }
    private void mark(char[][] b, int r, int c) {
        if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] != 'O') return;
        b[r][c] = 'S';
        mark(b, r + 1, c); mark(b, r - 1, c); mark(b, r, c + 1); mark(b, r, c - 1);
    }
  6. 6

    Keys and rooms: can you visit every room?

    medium

    Room 0 is open and each room contains keys to other rooms. DFS from room 0, visit each key once and check whether the number of visited rooms equals n. Time O(n + total keys), space O(n). Edge cases: keys that point to the current room, rooms with no keys, a locked room nobody has a key for.

    python
    def can_visit_all(rooms):
        seen, stack = {0}, [0]
        while stack:
            for k in rooms[stack.pop()]:
                if k not in seen:
                    seen.add(k)
                    stack.append(k)
        return len(seen) == len(rooms)
    java
    boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] seen = new boolean[rooms.size()];
        Deque<Integer> st = new ArrayDeque<>();
        st.push(0); seen[0] = true;
        int cnt = 1;
        while (!st.isEmpty())
            for (int k : rooms.get(st.pop()))
                if (!seen[k]) { seen[k] = true; cnt++; st.push(k); }
        return cnt == rooms.size();
    }
  7. 7

    Word search: does the word exist in the grid?

    medium

    Start a DFS at every cell matching the first letter. Match one letter per step, mark the current cell as used by overwriting it, explore four neighbours and restore the cell on the way back (backtracking). Prune on first mismatch. Time O(R * C * 3^L), space O(L) recursion. Edge cases: a word longer than the number of cells, reusing a cell (not allowed), restoring the cell even when the branch fails.

    python
    def exist(board, word):
        R, C = len(board), len(board[0])
        def dfs(r, c, i):
            if i == len(word):
                return True
            if not (0 <= r < R and 0 <= c < C) or board[r][c] != word[i]:
                return False
            tmp, board[r][c] = board[r][c], '#'
            found = (dfs(r+1, c, i+1) or dfs(r-1, c, i+1) or
                     dfs(r, c+1, i+1) or dfs(r, c-1, i+1))
            board[r][c] = tmp
            return found
        return any(dfs(r, c, 0) for r in range(R) for c in range(C))
    java
    boolean exist(char[][] b, String w) {
        for (int r = 0; r < b.length; r++)
            for (int c = 0; c < b[0].length; c++)
                if (dfs(b, w, r, c, 0)) return true;
        return false;
    }
    private boolean dfs(char[][] b, String w, int r, int c, int i) {
        if (i == w.length()) return true;
        if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] != w.charAt(i)) return false;
        char tmp = b[r][c];
        b[r][c] = '#';
        boolean found = dfs(b, w, r + 1, c, i + 1) || dfs(b, w, r - 1, c, i + 1)
                     || dfs(b, w, r, c + 1, i + 1) || dfs(b, w, r, c - 1, i + 1);
        b[r][c] = tmp;
        return found;
    }
  8. 8

    Pacific Atlantic water flow

    hard

    Water flows from a cell to equal or lower neighbours. Instead of testing every cell, search backwards: DFS inward from the Pacific border (top and left) moving to equal or higher cells, and the same from the Atlantic border (bottom and right). Cells reached by both searches are the answer. Time O(R * C), space O(R * C). Edge cases: one-row or one-column grids (every cell touches both oceans), plateaus of equal height, strict versus non-strict comparison direction.

    python
    def pacific_atlantic(h):
        R, C = len(h), len(h[0])
        def reach(starts):
            seen, stack = set(starts), list(starts)
            while stack:
                r, c = stack.pop()
                for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                    nr, nc = r + dr, c + dc
                    if (0 <= nr < R and 0 <= nc < C and (nr, nc) not in seen
                            and h[nr][nc] >= h[r][c]):
                        seen.add((nr, nc)); stack.append((nr, nc))
            return seen
        pac = reach([(r, 0) for r in range(R)] + [(0, c) for c in range(C)])
        atl = reach([(r, C-1) for r in range(R)] + [(R-1, c) for c in range(C)])
        return [list(p) for p in pac & atl]
    java
    List<List<Integer>> pacificAtlantic(int[][] h) {
        int R = h.length, C = h[0].length;
        boolean[][] pac = new boolean[R][C], atl = new boolean[R][C];
        for (int r = 0; r < R; r++) { dfs(h, r, 0, pac); dfs(h, r, C - 1, atl); }
        for (int c = 0; c < C; c++) { dfs(h, 0, c, pac); dfs(h, R - 1, c, atl); }
        List<List<Integer>> res = new ArrayList<>();
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                if (pac[r][c] && atl[r][c]) res.add(List.of(r, c));
        return res;
    }
    private void dfs(int[][] h, int r, int c, boolean[][] seen) {
        seen[r][c] = true;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nc >= 0 && nr < h.length && nc < h[0].length
                && !seen[nr][nc] && h[nr][nc] >= h[r][c]) dfs(h, nr, nc, seen);
        }
    }
  9. 9

    Longest increasing path in a matrix

    hard

    From each cell move to a strictly larger neighbour. Because values strictly increase there are no cycles, so DFS with memoisation is safe: memo[r][c] stores the longest path starting at that cell. Each cell is computed once. Time O(R * C), space O(R * C). Edge cases: all values equal (answer 1), recursion depth up to R*C on a spiral, strict versus non-strict increase.

    python
    def longest_increasing_path(m):
        R, C = len(m), len(m[0])
        memo = {}
        def dfs(r, c):
            if (r, c) in memo:
                return memo[(r, c)]
            best = 1
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < R and 0 <= nc < C and m[nr][nc] > m[r][c]:
                    best = max(best, 1 + dfs(nr, nc))
            memo[(r, c)] = best
            return best
        return max(dfs(r, c) for r in range(R) for c in range(C))
    java
    int longestIncreasingPath(int[][] m) {
        int[][] memo = new int[m.length][m[0].length];
        int best = 0;
        for (int r = 0; r < m.length; r++)
            for (int c = 0; c < m[0].length; c++) best = Math.max(best, dfs(m, r, c, memo));
        return best;
    }
    private int dfs(int[][] m, int r, int c, int[][] memo) {
        if (memo[r][c] != 0) return memo[r][c];
        int best = 1;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nc >= 0 && nr < m.length && nc < m[0].length && m[nr][nc] > m[r][c])
                best = Math.max(best, 1 + dfs(m, nr, nc, memo));
        }
        return memo[r][c] = best;
    }
  10. 10

    Find eventual safe states in a directed graph

    hard

    A node is safe if every path from it ends at a terminal node. Run DFS with three colours as in cycle detection: a node that reaches a cycle is unsafe, one that finishes without meeting a node on the current path is safe. Return safe nodes in sorted order. Time O(V + E), space O(V). Edge cases: self-loops (unsafe), isolated terminals (safe), nodes that only lead into a cycle.

    python
    def eventual_safe(graph):
        n = len(graph)
        state = [0] * n  # 0 new, 1 visiting, 2 safe
        def safe(u):
            if state[u]:
                return state[u] == 2
            state[u] = 1
            for v in graph[u]:
                if not safe(v):
                    return False
            state[u] = 2
            return True
        return [i for i in range(n) if safe(i)]
    java
    List<Integer> eventualSafeNodes(int[][] graph) {
        int[] state = new int[graph.length];
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < graph.length; i++) if (safe(graph, i, state)) res.add(i);
        return res;
    }
    private boolean safe(int[][] g, int u, int[] state) {
        if (state[u] != 0) return state[u] == 2;
        state[u] = 1;
        for (int v : g[u]) if (!safe(g, v, state)) return false;
        state[u] = 2;
        return true;
    }

Frequently asked questions

What is the difference between DFS and backtracking?

Backtracking is DFS over a decision tree with undo steps. You choose, recurse, then undo the choice so the next branch starts from a clean state.

Can DFS find the shortest path?

Not in an unweighted graph in general, because it may reach the target by a long route first. Use BFS for fewest edges.

How do I avoid stack overflow in DFS?

Use an explicit stack with a loop, or raise the recursion limit where the language allows. Mention this tradeoff when the input can be very large.

Which DFS problems are most common?

Number of islands, word search and clone graph appear very often. The online assessment guide explains how such tests are typically structured.

Related guides

More in DSA Interview Questions

See all in this section