Bird
Raised Fist0
DSA C#programming~5 mins

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

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Time Complexity: Word Search in Grid Using Backtracking
O(m * n * 4^k)
Understanding Time Complexity

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

How does the search time change when the grid or word gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


public bool Exist(char[][] board, string word) {
    for (int i = 0; i < board.Length; i++) {
        for (int j = 0; j < board[0].Length; j++) {
            if (Backtrack(board, word, i, j, 0)) return true;
        }
    }
    return false;
}

private bool Backtrack(char[][] board, string word, int i, int j, int index) {
    if (index == word.Length) return true;
    if (i < 0 || i >= board.Length || j < 0 || j >= board[0].Length || board[i][j] != word[index]) return false;

    char temp = board[i][j];
    board[i][j] = '#';

    bool found = Backtrack(board, word, i + 1, j, index + 1) ||
                 Backtrack(board, word, i - 1, j, index + 1) ||
                 Backtrack(board, word, i, j + 1, index + 1) ||
                 Backtrack(board, word, i, j - 1, index + 1);

    board[i][j] = temp;
    return found;
}

This code tries to find a word in a 2D grid by checking each cell and exploring neighbors recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

  • Primary operation: The recursive backtracking call that explores up to 4 directions for each character in the word.
  • How many times: For each cell in the grid (m rows * n columns), it may explore up to 4 recursive calls for each character in the word (length k).
How Execution Grows With Input

The search tries starting from every cell, and for each character in the word, it explores up to 4 directions. This means the operations grow very fast as the word length increases.

Input Size (word length k)Approx. Operations
10Up to 4^10 * m * n (about 1 million times grid size)
100Up to 4^100 * m * n (an extremely large number)
1000Up to 4^1000 * m * n (practically impossible to compute)

Pattern observation: The number of operations grows exponentially with the word length, making the search very costly for long words.

Final Time Complexity

Time Complexity: O(m * n * 4^k)

This means the time needed grows very fast as the word length (k) increases, since each character can lead to 4 new searches from each cell in the grid.

Common Mistake

[X] Wrong: "The search only checks each cell once, so it should be fast even for long words."

[OK] Correct: The search explores many paths recursively for each character, so it can revisit cells in different paths, causing exponential growth in operations.

Interview Connect

Understanding this complexity helps you explain why backtracking can be slow and when to use it. It shows your skill in analyzing recursive searches and their costs.

Self-Check

"What if we added memoization to remember visited states? How would the time complexity change?"

Practice

(1/5)
1. What is the main purpose of backtracking in the Word Search problem on a grid?
easy
A. To count the number of words in the grid
B. To sort the grid alphabetically
C. To explore all possible paths to find the word
D. To replace characters in the grid

Solution

  1. Step 1: Understand backtracking role

    Backtracking tries all possible paths in the grid to find the target word by moving in allowed directions.

  2. Step 2: Eliminate other options

    Sorting, counting, or replacing characters are unrelated to the search process using backtracking.

  3. Final Answer:

    To explore all possible paths to find the word -> Option C

  4. Quick Check:

    Backtracking = Explore paths [OK]
Hint: Backtracking explores paths step-by-step to find the word [OK]
Common Mistakes:
  • Thinking backtracking sorts or modifies the grid
  • Confusing backtracking with counting words
  • Assuming backtracking replaces characters permanently
2. Which of the following is the correct way to check if the next cell is within grid bounds in C#?
easy
A. if (row >= 0 && row < grid.Length && col >= 0 && col < grid[0].Length)
B. if (row > 0 && row <= grid.Length && col > 0 && col <= grid[0].Length)
C. if (row >= 0 && row <= grid.Length && col >= 0 && col <= grid[0].Length)
D. if (row > 0 && row < grid.Length && col > 0 && col < grid[0].Length)

Solution

  1. Step 1: Understand grid indexing in C#

    Grid rows and columns are zero-indexed, so valid indices are from 0 to Length-1.

  2. Step 2: Check boundary conditions

    if (row >= 0 && row < grid.Length && col >= 0 && col < grid[0].Length) correctly checks if row and col are >= 0 and less than Length, ensuring valid indices.

  3. Final Answer:

    if (row >= 0 && row < grid.Length && col >= 0 && col < grid[0].Length) -> Option A

  4. Quick Check:

    Bounds check uses >=0 and < Length [OK]
Hint: Use >=0 and < Length for zero-based index checks [OK]
Common Mistakes:
  • Using > 0 excludes first row/column
  • Using <= Length causes out-of-range errors
  • Confusing row and column length checks
3. What will be the output of the following C# code snippet for word search?
char[][] grid = {
  new char[] {'A','B','C','E'},
  new char[] {'S','F','C','S'},
  new char[] {'A','D','E','E'}
};
string word = "ABCCED";
bool result = WordSearch(grid, word);
Console.WriteLine(result);

Assuming WordSearch uses backtracking correctly to find the word in the grid.
medium
A. True
B. False
C. Compilation error
D. Runtime exception

Solution

  1. Step 1: Analyze the grid and word

    The word "ABCCED" can be found by moving right and down starting at grid[0][0]: A->B->C->C->E->D.

  2. Step 2: Confirm backtracking finds the word

    Backtracking explores all paths and will find this sequence, so result is true.

  3. Final Answer:

    True -> Option A

  4. Quick Check:

    Word found in grid = True [OK]
Hint: Trace word path step-by-step in grid to confirm presence [OK]
Common Mistakes:
  • Assuming word is not found without tracing path
  • Confusing similar letters in grid
  • Ignoring backtracking's ability to explore all paths
4. Identify the bug in this backtracking snippet for word search:
bool Backtrack(char[][] grid, string word, int index, int row, int col) {
  if (index == word.Length) return true;
  if (row < 0 || row >= grid.Length || col < 0 || col >= grid[0].Length) return false;
  if (grid[row][col] != word[index]) return false;
  char temp = grid[row][col];
  grid[row][col] = '#';
  bool found = Backtrack(grid, word, index + 1, row + 1, col) ||
               Backtrack(grid, word, index + 1, row - 1, col) ||
               Backtrack(grid, word, index + 1, row, col + 1) ||
               Backtrack(grid, word, index + 1, row, col - 1);
  grid[row][col] = temp;
  return found;
}
medium
A. The grid cell is not restored after recursion
B. The function does not check for visited cells properly
C. The base case should check index > word.Length
D. The function does not check grid boundaries before accessing

Solution

  1. Step 1: Check visited cell marking

    The code marks visited cells by replacing with '#', which prevents revisiting during recursion.

  2. Step 2: Identify missing visited check

    However, the code does not check if the current cell is '#' before comparing with word[index], so it may revisit marked cells incorrectly.

  3. Final Answer:

    The function does not check for visited cells properly -> Option B

  4. Quick Check:

    Visited check missing = Bug [OK]
Hint: Always check if cell is visited before matching character [OK]
Common Mistakes:
  • Forgetting to check if cell is marked visited
  • Incorrect base case condition
  • Not restoring grid cell after recursion
5. Given a 4x4 grid:
char[][] grid = {
  new char[] {'C','A','T','F'},
  new char[] {'B','G','E','S'},
  new char[] {'I','T','A','E'},
  new char[] {'S','O','N','G'}
};

Which of the following words cannot be found using backtracking moving only up, down, left, or right?
hard
A. "CAT"
B. "GATE"
C. "SONG"
D. "BATS"

Solution

  1. Step 1: Check presence of each word

    "CAT" is in first row (C->A->T). "SONG" is in last row (S->O->N->G). "GATE" can be formed by G->A->T->E in middle rows.

  2. Step 2: Verify "BATS" formation

    "BATS" requires B->A->T->S. B is at grid[1][0], but no path connects A and T and then S in sequence moving only up/down/left/right without skipping letters.

  3. Final Answer:

    "BATS" cannot be found -> Option D

  4. Quick Check:

    Word path missing = "BATS" [OK]
Hint: Trace each letter path carefully to confirm word presence [OK]
Common Mistakes:
  • Assuming all words are present without path check
  • Ignoring movement restrictions (no diagonals)
  • Confusing letter positions in grid
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard