How does Interview Prep handle grid DFS?

Interview Prep covers this with 2 copy-ready snippets on this page. The "Number of Islands" snippet in Interview Prep uses `Treat grid as a graph. Each '1' cell is a node, connected to 4-directional '1' neighbors.`.

What other Interview Prep snippets are shown for "grid DFS"?

Besides "Number of Islands", this page also shows "Word Search in Grid".

Grid DFS

2 snippets in Interview Prep

DSAInterview Prep

Number of Islands

DSA · Graphs

Syntax

Treat grid as a graph. Each '1' cell is a node, connected to 4-directional '1' neighbors.
BFS or DFS from each unvisited '1'. Count how many searches you start.

Example

// JavaScript
function numIslands(grid) {
  if (!grid.length) return 0;
  const rows = grid.length, cols = grid[0].length;
  let count = 0;
  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return;
    grid[r][c] = '0'; // mark visited
    dfs(r + 1, c); dfs(r - 1, c);
    dfs(r, c + 1); dfs(r, c - 1);
  }
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

# Python
def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'
        dfs(r + 1, c); dfs(r - 1, c)
        dfs(r, c + 1); dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

Output

Grid:
1 1 0 0
1 0 0 1
0 0 1 1
→ 3 islands

Note Time O(rows * cols), Space O(rows * cols) worst case for recursion stack. Modifying the input grid to mark visited saves space but is destructive - ask the interviewer if that is acceptable. BFS alternative avoids deep recursion. Variants: max area of island, surrounded regions.

Word Search in Grid

DSA · Recursion & Backtracking

Syntax

DFS from each cell. At each step, check if the current cell matches the next character.
Mark cell as visited (temporarily modify it), recurse in 4 directions, then unmark.

Example

// JavaScript
function exist(board, word) {
  const rows = board.length, cols = board[0].length;
  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] !== word[idx]) return false;
    const saved = board[r][c];
    board[r][c] = '#'; // mark visited
    const found = dfs(r+1,c,idx+1) || dfs(r-1,c,idx+1)
               || dfs(r,c+1,idx+1) || dfs(r,c-1,idx+1);
    board[r][c] = saved; // unmark
    return found;
  }
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (dfs(r, c, 0)) return true;
  return false;
}

# Python
def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, idx):
        if idx == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if board[r][c] != word[idx]:
            return False
        saved = board[r][c]
        board[r][c] = '#'
        found = (dfs(r+1,c,idx+1) or dfs(r-1,c,idx+1)
                 or dfs(r,c+1,idx+1) or dfs(r,c-1,idx+1))
        board[r][c] = saved
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Output

board = [['A','B','C','E'],
         ['S','F','C','S'],
         ['A','D','E','E']]
exist(board, 'ABCCED') → True

Note Time O(m * n * 4^L) where L = word length. The temporary cell modification is a clean alternative to a separate visited set. Always restore the cell after backtracking. Optimization: check if the board has all needed characters before starting DFS.

Frequently asked questions

How does Interview Prep handle grid DFS?: Interview Prep covers this with 2 copy-ready snippets on this page. The "Number of Islands" snippet in Interview Prep uses `Treat grid as a graph. Each '1' cell is a node, connected to 4-directional '1' neighbors.`.
Which code does the Interview Prep example use?: The "Number of Islands" snippet uses `Treat grid as a graph. Each '1' cell is a node, connected to 4-directional '1' neighbors.`, from the Graphs section of the Interview Prep cheat sheet.
What other Interview Prep snippets are shown for "grid DFS"?: Besides "Number of Islands", this page also shows "Word Search in Grid".
Is there anything to watch out for?: Yes. For "Number of Islands": Time O(rows * cols), Space O(rows * cols) worst case for recursion stack. Modifying the input grid to mark visited saves space but is destructive - ask the interviewer if that is acceptable. BFS alternative avoids deep recursion. Variants: max area of island, surrounded regions.