Skip to main content

59. Word Search

mediumAsked at Datadog

Determine if a word exists in a 2D board where adjacent cells form a path. Datadog uses this for the DFS-with-backtracking pattern — same shape as searching for a metric-name pattern in a hierarchical store.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite DFS question.

Problem

Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Constraints

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consists of only lowercase and uppercase English letters.

Examples

Example 1

Input
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output
true

Example 2

Input
board = same, word = "SEE"
Output
true

Example 3

Input
board = same, word = "ABCB"
Output
false

Approaches

1. DFS with separate visited matrix

Standard DFS from each cell; allocate visited[][] to avoid revisits.

Time
O(m * n * 4^L)
Space
O(m * n + L)
// DFS from each starting cell with a boolean visited matrix.

Tradeoff: Extra memory for visited. Datadog will push for the in-place mark.

2. DFS with in-place mark (optimal)

Temporarily overwrite visited cells with a sentinel (e.g., '#'). Restore on backtrack.

Time
O(m * n * 4^L)
Space
O(L) recursion
function exist(board, word) {
  const m = board.length, n = board[0].length;
  function dfs(r, c, i) {
    if (i === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[i]) return false;
    const tmp = board[r][c];
    board[r][c] = '#';
    const found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1) || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
    board[r][c] = tmp;
    return found;
  }
  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) if (dfs(r, c, 0)) return true;
  return false;
}

Tradeoff: O(L) extra (recursion only). Datadog-canonical: in-place marking is the same pattern as their write-through marker for active paths.

Datadog-specific tips

Datadog grades on the in-place marking — it's the cleaner approach because visited state is naturally tied to the recursion. Articulate the save-mark-recurse-restore pattern BEFORE coding.

Common mistakes

  • Forgetting to restore the cell after recursion — corrupts the board for other start cells.
  • Putting the bounds check inside the for-loop callers instead of inside dfs — duplicates code.
  • Checking word[i] BEFORE bounds — null dereference.

Follow-up questions

An interviewer at Datadog may pivot to one of these next:

  • Word Search II (LC 212) — many words at once; use Trie.
  • Robot Bounded in Circle — different path-following.
  • Datadog-style: search for a metric-pattern in a hierarchical store.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why mark in place instead of using visited?

Saves memory; the cell value itself carries the visited info. Restore on backtrack so other DFS starts see the original board.

Best-case pruning?

If any character in word doesn't appear in board at all, return false immediately. Saves the full DFS.

Practice these live with InterviewChamp.AI

Drill Word Search and other Datadog interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →