What happens if you not marking visited cells properly?

Leads to revisiting cells and infinite recursion or incorrect matches Fix: Mark cells as visited before recursion and restore after (backtracking)

What happens if you not checking boundary conditions before accessing board?

Causes index out of bounds runtime errors Fix: Always check row and column indices before accessing board cells

What happens if you trying to reuse the same cell multiple times in one path?

Incorrectly finds words that are not valid according to problem rules Fix: Use visited marking to prevent reusing cells in the current path

What happens if you not returning early when word is found?

Unnecessary exploration leads to timeouts Fix: Return true immediately when all characters matched

Interview PrepbacktrackingmediumAmazonFacebookGoogleBloomberg

Word Search

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

Word Search

mediumBACKTRACKINGAmazonFacebookGoogle

Imagine you have a crossword puzzle grid and a word list. You want to find if a particular word can be traced in the grid by moving horizontally or vertically, letter by letter.

💡 This problem is about searching for a sequence of characters in a 2D grid by exploring all possible paths. Beginners often struggle because it requires careful backtracking and marking visited cells to avoid revisiting and infinite loops.

📋

Problem Statement

Given a 2D board of characters and a word, determine if the 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.

1 ≤ board.length ≤ 2001 ≤ board[i].length ≤ 2001 ≤ word.length ≤ 10^3board and word consist only of uppercase and lowercase English letters

💡

Example

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

Outputtrue

The word 'ABCCED' can be found by the path A->B->C->C->E->D in the grid.

Input"board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = 'SEE'"

Outputtrue

The word 'SEE' can be found by the path S->E->E.

Input"board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = 'ABCB'"

Outputfalse

The word 'ABCB' cannot be found because the letter 'B' cannot be reused.

Empty board → false
Word longer than total cells → false
Word is a single letter present in board → true
Board with all identical letters and word repeating that letter → true if length fits

⚠️

Common Mistakes

Not marking visited cells properly

Leads to revisiting cells and infinite recursion or incorrect matches

✅ Mark cells as visited before recursion and restore after (backtracking)

Not checking boundary conditions before accessing board

Causes index out of bounds runtime errors

✅ Always check row and column indices before accessing board cells

Trying to reuse the same cell multiple times in one path

Incorrectly finds words that are not valid according to problem rules

✅ Use visited marking to prevent reusing cells in the current path

Not returning early when word is found

Unnecessary exploration leads to timeouts

✅ Return true immediately when all characters matched

Modifying the board permanently without restoring

Subsequent searches fail due to corrupted board state

✅ Restore the board cell after backtracking

🧠

Brute Force (Pure Recursion with Backtracking)

💡 This approach is the foundation for understanding the problem. It tries every possible path starting from each cell, which is simple but inefficient.

Intuition

Try to find the word starting from every cell. For each cell, recursively explore its neighbors to match the next character, marking cells visited to avoid reuse.

Algorithm

For each cell in the grid, start a DFS if the cell matches the first character of the word.
In DFS, check if the current cell matches the current character in the word.
Mark the cell as visited to avoid revisiting in the current path.
Recursively explore all 4 directions (up, down, left, right) for the next character.
If all characters are matched, return true; else backtrack and unmark the cell.

💡 The challenge is to carefully manage visited cells and backtrack correctly to explore all paths without repetition.

</>

Code

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        
        def dfs(r, c, index):
            if index == len(word):
                return True
            if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[index]:
                return False
            temp = board[r][c]
            board[r][c] = '#'
            found = (dfs(r+1, c, index+1) or dfs(r-1, c, index+1) or
                     dfs(r, c+1, index+1) or dfs(r, c-1, index+1))
            board[r][c] = temp
            return found
        
        for i in range(rows):
            for j in range(cols):
                if board[i][j] == word[0] and dfs(i, j, 0):
                    return True
        return False

# Example usage:
# sol = Solution()
# print(sol.exist([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABCCED'))  # True

Line Notes

def exist(self, board: List[List[str]], word: str) -> bool:Defines the main function with board and word inputs

rows, cols = len(board), len(board[0])Store dimensions to avoid repeated calls

def dfs(r, c, index):Helper function to perform DFS from cell (r,c) matching word[index]

if index == len(word):Base case: all characters matched successfully

if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[index]:Boundary and character mismatch check

temp = board[r][c]Save current cell character before marking visited

board[r][c] = '#'Mark cell as visited to avoid reuse in current path

found = (dfs(r+1, c, index+1) or dfs(r-1, c, index+1) or dfs(r, c+1, index+1) or dfs(r, c-1, index+1))Explore all 4 directions recursively

board[r][c] = tempRestore cell after exploring all paths (backtracking)

for i in range(rows):Try starting DFS from every cell in the grid

if board[i][j] == word[0] and dfs(i, j, 0):Start DFS only if first character matches

public class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length, cols = board[0].length;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == word.charAt(0) && dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int r, int c, int index) {
        if (index == word.length()) return true;
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(index))
            return false;
        char temp = board[r][c];
        board[r][c] = '#';
        boolean found = dfs(board, word, r + 1, c, index + 1) ||
                        dfs(board, word, r - 1, c, index + 1) ||
                        dfs(board, word, r, c + 1, index + 1) ||
                        dfs(board, word, r, c - 1, index + 1);
        board[r][c] = temp;
        return found;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     Solution sol = new Solution();
    //     char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
    //     System.out.println(sol.exist(board, "ABCCED")); // true
    // }
}

Line Notes

public boolean exist(char[][] board, String word)Main method signature for the problem

for (int i = 0; i < rows; i++)Iterate over each row to start DFS

if (board[i][j] == word.charAt(0) && dfs(board, word, i, j, 0))Start DFS only if first character matches

private boolean dfs(char[][] board, String word, int r, int c, int index)DFS helper to explore paths

if (index == word.length()) return true;Base case: all characters matched

if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(index)) return false;Boundary and mismatch check

char temp = board[r][c];Save current cell before marking visited

board[r][c] = '#';Mark cell visited to avoid reuse

boolean found = dfs(...) || dfs(...) || dfs(...) || dfs(...)Explore all 4 directions recursively

board[r][c] = temp;Restore cell after recursion (backtracking)

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int rows = board.size(), cols = board[0].size();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == word[0] && dfs(board, word, i, j, 0))
                    return true;
            }
        }
        return false;
    }

private:
    bool dfs(vector<vector<char>>& board, const string& word, int r, int c, int index) {
        if (index == word.size()) return true;
        if (r < 0 || r >= (int)board.size() || c < 0 || c >= (int)board[0].size() || board[r][c] != word[index])
            return false;
        char temp = board[r][c];
        board[r][c] = '#';
        bool found = dfs(board, word, r + 1, c, index + 1) ||
                     dfs(board, word, r - 1, c, index + 1) ||
                     dfs(board, word, r, c + 1, index + 1) ||
                     dfs(board, word, r, c - 1, index + 1);
        board[r][c] = temp;
        return found;
    }

// Example usage:
// int main() {
//     Solution sol;
//     vector<vector<char>> board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
//     bool res = sol.exist(board, "ABCCED");
//     return 0;
// }

Line Notes

bool exist(vector<vector<char>>& board, string word)Main function signature

for (int i = 0; i < rows; i++)Loop over rows to start DFS

if (board[i][j] == word[0] && dfs(board, word, i, j, 0))Start DFS only if first character matches

bool dfs(vector<vector<char>>& board, const string& word, int r, int c, int index)DFS helper function

if (index == word.size()) return true;Base case: all characters matched

if (r < 0 || r >= (int)board.size() || c < 0 || c >= (int)board[0].size() || board[r][c] != word[index]) return false;Boundary and mismatch check

char temp = board[r][c];Save current cell before marking visited

board[r][c] = '#';Mark cell visited to avoid reuse

bool found = dfs(...) || dfs(...) || dfs(...) || dfs(...)Explore all 4 directions recursively

board[r][c] = temp;Restore cell after recursion (backtracking)

var exist = function(board, word) {
    const rows = board.length, cols = board[0].length;
    
    function dfs(r, c, index) {
        if (index === word.length) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[index]) return false;
        const temp = board[r][c];
        board[r][c] = '#';
        const found = dfs(r + 1, c, index + 1) || dfs(r - 1, c, index + 1) || dfs(r, c + 1, index + 1) || dfs(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 (board[i][j] === word[0] && dfs(i, j, 0)) return true;
        }
    }
    return false;
};

// Example usage:
// console.log(exist([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABCCED')); // true

Line Notes

var exist = function(board, word)Main function declaration

const rows = board.length, cols = board[0].length;Store board dimensions

function dfs(r, c, index)DFS helper function to explore paths

if (index === word.length) return true;Base case: all characters matched

if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[index]) return false;Boundary and mismatch check

const temp = board[r][c];Save current cell before marking visited

board[r][c] = '#';Mark cell visited to avoid reuse

const found = dfs(...) || dfs(...) || dfs(...) || dfs(...)Explore all 4 directions recursively

board[r][c] = temp;Restore cell after recursion (backtracking)

for (let i = 0; i < rows; i++)Try starting DFS from every cell

⏱

Complexity

TimeO(N * 3^L) where N is number of cells and L is length of the word

SpaceO(L) recursion stack for the word length

From each cell, we explore up to 4 directions but avoid going back, so roughly 3 directions per step for L steps, repeated for each cell

💡 For a 10x10 board and word length 5, this could mean up to 100 * 3^5 = 24300 operations, which is feasible but grows quickly.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is slow for large boards or long words, so we need to optimize.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(N * 3^L)`	`O(L)`	Yes (deep recursion possible)	N/A	Mention only - never code
2. Backtracking with Early Pruning	`O(N * 3^L) but faster in practice`	`O(L)`	Yes	N/A	Mention as optimization
3. Backtracking with Directions Array	`O(N * 3^L)`	`O(L)`	Yes	N/A	Code this approach

Practice

(1/5)

1. Consider the following BFS-based code snippet for removing invalid parentheses:

from collections import deque

def is_valid(s: str) -> bool:
    count = 0
    for c in s:
        if c == '(': count += 1
        elif c == ')':
            count -= 1
            if count < 0:
                return False
    return count == 0

def remove_invalid_parentheses_bfs(s: str):
    res = []
    visited = set([s])
    queue = deque([s])
    found = False

    while queue:
        size = len(queue)
        for _ in range(size):
            curr = queue.popleft()
            if is_valid(curr):
                res.append(curr)
                found = True
            if found:
                continue
            for i in range(len(curr)):
                if curr[i] not in ('(', ')'):
                    continue
                next_str = curr[:i] + curr[i+1:]
                if next_str not in visited:
                    visited.add(next_str)
                    queue.append(next_str)
    return res

print(remove_invalid_parentheses_bfs("()())()"))

What is the output of this code?

easy

A. ["()()()"]

B. ["()()()", "(())()"]

C. ["(())()"]

D. ["()())()"]

3. The following code attempts to generate all permutations of a list using Heap's algorithm but contains a subtle bug:

def permute(nums):
    res = [nums[:]]
    c = [0] * len(nums)
    i = 0
    while i < len(nums):
        if c[i] < i:
            if i % 2 == 0:
                nums[0], nums[i] = nums[i], nums[0]
            else:
                nums[c[i]], nums[i] = nums[i], nums[c[i]]
            res.append(nums)
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return res

What is the bug in this code?

medium

A. The used array c is not reset properly, causing infinite loop

B. Appending nums directly without copying causes all entries in res to reference the same list

C. Swapping nums[0] and nums[i] when i is even is incorrect logic

D. The initial res list should be empty, not contain nums[:] at start

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

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Trace BFS levels for input "()())()"

Step 2: Confirm both valid strings are collected

Final Answer:

Quick Check:

Solution

Step 1: Identify complexity of outer and inner loops

Step 2: Check if pruning duplicates reduces complexity

Final Answer:

Quick Check:

Solution

Step 1: Identify how results are stored

Step 2: Understand consequences of appending references

Final Answer:

Quick Check:

Solution

Step 1: Identify branching factor per segment

Step 2: Calculate total combinations

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem variant

Step 2: Identify correct approach

Final Answer:

Quick Check:

Ready to prove it?