Grid DFS

Number of Islands

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.

DSAInterview Prep