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 structure | Recursion or explicit stack |
|---|---|
| Cost | O(V + E), or O(R * C) on a grid |
| Best for | Components, cycles, backtracking, path existence |
| Risk | Recursion 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
- Skipping the bounds check before reading the grid cell.
- Forgetting to restore the cell after a failed backtracking branch.
- Letting a DFS loop forever, for example in flood fill when the new colour equals the old.
- Recursing 10^6 deep on a large grid. Python defaults to about 1000 frames and Java to a few thousand, so mention an explicit stack.
- Using a boolean visited array for directed cycles when three states are needed.
DFS (Depth-First Search) Interview Questions: questions with worked answers
1 Flood fill
easyRemember 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.
pythondef 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 imgjavaint[][] 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 Number of islands
mediumScan 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.
pythondef 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 countjavaint 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 Maximum area of an island
mediumSame 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.
pythondef 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))javaint 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 Number of provinces from an adjacency matrix
mediumisConnected[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.
pythondef 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 countjavaint 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 Surrounded regions: capture O regions not touching the border
mediumWork 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.
pythondef 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'javavoid 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 Keys and rooms: can you visit every room?
mediumRoom 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.
pythondef 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)javaboolean 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 Word search: does the word exist in the grid?
mediumStart 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.
pythondef 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))javaboolean 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 Pacific Atlantic water flow
hardWater 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.
pythondef 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]javaList<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 Longest increasing path in a matrix
hardFrom 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.
pythondef 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))javaint 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 Find eventual safe states in a directed graph
hardA 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.
pythondef 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)]javaList<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
- Dijkstra and Shortest Path Interview Questions
- Divide and Conquer Interview Questions
- Dynamic Programming Interview Questions
- Edit Distance and String DP Interview Questions
- Fast and slow pointers interview questions with solutions
- Fenwick Tree (Binary Indexed Tree) Interview Questions
- Graph Interview Questions and Answers
- Greedy algorithm interview questions with worked solutions
- Grid and Matrix DP Interview Questions
- Hashing interview questions with worked solutions
- Heap and Priority Queue Interview Questions
- Interval DP Interview Questions