Word Search in Grid Using Backtracking in DSA Typescript - Time & Space Complexity

Time Complexity: Word Search in Grid Using Backtracking

O(N * 4^M)

Understanding Time Complexity

We want to understand how the time needed to find a word in a grid grows as the grid and word sizes increase.

Specifically, how does the search time change when we try all possible paths to match the word?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function exist(board: string[][], word: string): boolean {
  const rows = board.length;
  const cols = board[0].length;

  function backtrack(r: number, c: number, index: number): boolean {
    if (index === word.length) return true;
    if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== word[index]) return false;

    const temp = board[r][c];
    board[r][c] = '#';

    const found = backtrack(r+1, c, index+1) || backtrack(r-1, c, index+1) || backtrack(r, c+1, index+1) || backtrack(r, c-1, index+1);

    board[r][c] = temp;
    return found;
  }

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (backtrack(i, j, 0)) return true;
    }
  }
  return false;
}
    

This code tries to find the given word in the grid by exploring all possible paths using backtracking.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The recursive backtracking function explores up to 4 directions for each letter in the word.
• How many times: For each cell in the grid (rows * cols), it may explore up to 4 choices for each character in the word (word length).

How Execution Grows With Input

As the grid size and word length grow, the number of paths to check grows very fast.

Input Size (n = rows * cols)	Word Length (m)	Approx. Operations
10	3	About 10 * 4^3 = 640
100	5	About 100 * 4^5 = 10,2400
1000	6	About 1000 * 4^6 = 4,096,000

Pattern observation: The operations grow exponentially with the word length and linearly with the grid size.

Final Time Complexity

Time Complexity: O(N * 4^M)

This means the time grows linearly with the number of cells in the grid and exponentially with the length of the word.

Common Mistake

[X] Wrong: "The search only takes time proportional to the grid size because we just check each cell once."

[OK] Correct: Because the search explores many paths recursively for each letter, it can revisit cells in different paths, causing exponential growth with word length.

Interview Connect

Understanding this complexity helps you explain how backtracking explores many possibilities and why pruning or constraints matter in real problems.

Self-Check

"What if we limited the search to only horizontal and vertical directions instead of all four directions? How would the time complexity change?"