What happens if you not marking visited cells properly?

Leads to revisiting same cell multiple times causing incorrect matches or infinite recursion Fix: Use a visited set or in-place marking to track visited cells during backtracking

What happens if you not pruning trie nodes after word found?

Leads to redundant searches and slower runtime Fix: Remove trie nodes with no children after word is found to reduce search space

What happens if you returning duplicates of found words?

Output contains repeated words Fix: Mark found words as None/null in trie to avoid adding duplicates

What happens if you not handling empty board or words list?

Code may crash or return incorrect results Fix: Add checks for empty inputs and return empty list early

Interview Prepchallenge-problemshardAmazonFacebookGoogleBloomberg

Word Search II

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

Word Search II

hardMIXEDAmazonFacebookGoogle

Imagine you have a large grid of letters and a dictionary of words. Your task is to find all words from the dictionary that can be formed by tracing adjacent letters in the grid, like a word puzzle challenge.

💡 This problem combines searching in a 2D grid with efficient prefix checking. Beginners often struggle because naive search is too slow, and understanding how to prune searches using tries is key to solving it efficiently.

📋

Problem Statement

Given a 2D board of characters and a list of words, find all words in the board. Each word must 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 in a word. Return all words found in the board.

1 <= board.length <= 121 <= board[i].length <= 121 <= words.length <= 3 * 10^41 <= words[i].length <= 10board and words[i] consist of lowercase English letters

💡

Example

Input

"board = [[\"o\",\"a\",\"a\",\"n\"],[\"e\",\"t\",\"a\",\"e\"],[\"i\",\"h\",\"k\",\"r\"],[\"i\",\"f\",\"l\",\"v\"]], words = [\"oath\",\"pea\",\"eat\",\"rain\"]"

Output["oath","eat"]

The words 'eat' and 'oath' can be formed by adjacent letters in the board, while 'pea' and 'rain' cannot.

Empty board → returns empty list
Empty words list → returns empty list
Words with repeated letters that require revisiting cells → should not be found
Board with all identical letters and words that are substrings → finds correct matches

⚠️

Common Mistakes

Not marking visited cells properly

Leads to revisiting same cell multiple times causing incorrect matches or infinite recursion

✅ Use a visited set or in-place marking to track visited cells during backtracking

Not pruning trie nodes after word found

Leads to redundant searches and slower runtime

✅ Remove trie nodes with no children after word is found to reduce search space

Returning duplicates of found words

Output contains repeated words

✅ Mark found words as None/null in trie to avoid adding duplicates

Not handling empty board or words list

Code may crash or return incorrect results

✅ Add checks for empty inputs and return empty list early

Modifying board without restoring

Leads to incorrect results for subsequent searches

✅ Always restore board cell after backtracking recursion

🧠

Brute Force (Backtracking for Each Word)

💡 This approach tries to find each word independently by searching the entire board for its first letter and then backtracking to check if the word can be formed. It is simple but inefficient for large inputs.

Intuition

For each word, scan the board to find starting points matching the first letter, then recursively explore neighbors to match subsequent letters, marking visited cells to avoid reuse.

Algorithm

For each word in the list:
For each cell in the board:
If the cell matches the first letter of the word, start backtracking from there.
Backtracking explores adjacent cells recursively to match the next letter, marking cells visited to avoid reuse.

💡 The nested loops and recursion make it hard to see the exponential time complexity at first, but it's a straightforward exhaustive search.

</>

Code

from typing import List

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        ROWS, COLS = len(board), len(board[0])
        res = []

        def backtrack(r, c, word, index, visited):
            if index == len(word):
                return True
            if r < 0 or c < 0 or r >= ROWS or c >= COLS:
                return False
            if (r, c) in visited or board[r][c] != word[index]:
                return False

            visited.add((r, c))
            # Explore neighbors
            found = (backtrack(r+1, c, word, index+1, visited) or
                     backtrack(r-1, c, word, index+1, visited) or
                     backtrack(r, c+1, word, index+1, visited) or
                     backtrack(r, c-1, word, index+1, visited))
            visited.remove((r, c))
            return found

        for word in words:
            found_word = False
            for r in range(ROWS):
                for c in range(COLS):
                    if board[r][c] == word[0]:
                        if backtrack(r, c, word, 0, set()):
                            res.append(word)
                            found_word = True
                            break
                if found_word:
                    break
        return res

# Example usage:
if __name__ == '__main__':
    board = [
        ['o','a','a','n'],
        ['e','t','a','e'],
        ['i','h','k','r'],
        ['i','f','l','v']
    ]
    words = ["oath","pea","eat","rain"]
    sol = Solution()
    print(sol.findWords(board, words))

Line Notes

def backtrack(r, c, word, index, visited):Defines recursive function to explore board for current word index to match letters sequentially.

if index == len(word):Base case: all letters matched successfully, so return True to indicate word found.

if (r, c) in visited or board[r][c] != word[index]:Prune paths that revisit cells or where current cell letter doesn't match the word's current letter.

visited.add((r, c))Mark current cell as visited to avoid reuse in the same word path.

visited.remove((r, c))Backtrack by unmarking cell after exploring all neighbors to allow other paths to use it.

for word in words:Iterate over all words independently, performing a fresh search for each.

if backtrack(r, c, word, 0, set()):Start backtracking from cells matching the first letter of the current word.

import java.util.*;

public class Solution {
    private int ROWS, COLS;
    private char[][] board;

    public List<String> findWords(char[][] board, String[] words) {
        this.board = board;
        ROWS = board.length;
        COLS = board[0].length;
        List<String> res = new ArrayList<>();

        for (String word : words) {
            boolean found = false;
            for (int r = 0; r < ROWS && !found; r++) {
                for (int c = 0; c < COLS && !found; c++) {
                    if (board[r][c] == word.charAt(0)) {
                        if (backtrack(r, c, word, 0, new boolean[ROWS][COLS])) {
                            res.add(word);
                            found = true;
                        }
                    }
                }
            }
        }
        return res;
    }

    private boolean backtrack(int r, int c, String word, int index, boolean[][] visited) {
        if (index == word.length()) return true;
        if (r < 0 || c < 0 || r >= ROWS || c >= COLS) return false;
        if (visited[r][c] || board[r][c] != word.charAt(index)) return false;

        visited[r][c] = true;
        boolean found = backtrack(r + 1, c, word, index + 1, visited) ||
                        backtrack(r - 1, c, word, index + 1, visited) ||
                        backtrack(r, c + 1, word, index + 1, visited) ||
                        backtrack(r, c - 1, word, index + 1, visited);
        visited[r][c] = false;
        return found;
    }

    // Example usage
    public static void main(String[] args) {
        char[][] board = {
            {'o','a','a','n'},
            {'e','t','a','e'},
            {'i','h','k','r'},
            {'i','f','l','v'}
        };
        String[] words = {"oath","pea","eat","rain"};
        Solution sol = new Solution();
        System.out.println(sol.findWords(board, words));
    }
}

Line Notes

private boolean backtrack(int r, int c, String word, int index, boolean[][] visited)Recursive helper to explore board for current word index, checking boundaries and visited cells.

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

if (visited[r][c] || board[r][c] != word.charAt(index)) return false;Prune invalid paths where cell is visited or letter mismatch.

visited[r][c] = true;Mark cell visited before recursion to avoid reuse.

visited[r][c] = false;Unmark cell after recursion to backtrack and allow other paths.

for (String word : words)Iterate over all words independently to find each separately.

if (board[r][c] == word.charAt(0))Start backtracking from cells matching the first letter of the word.

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

class Solution {
    int ROWS, COLS;
    vector<vector<char>> board;

    bool backtrack(int r, int c, const string& word, int index, vector<vector<bool>>& visited) {
        if (index == word.size()) return true;
        if (r < 0 || c < 0 || r >= ROWS || c >= COLS) return false;
        if (visited[r][c] || board[r][c] != word[index]) return false;

        visited[r][c] = true;
        bool found = backtrack(r+1, c, word, index+1, visited) ||
                     backtrack(r-1, c, word, index+1, visited) ||
                     backtrack(r, c+1, word, index+1, visited) ||
                     backtrack(r, c-1, word, index+1, visited);
        visited[r][c] = false;
        return found;
    }

public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        this->board = board;
        ROWS = board.size();
        COLS = board[0].size();
        vector<string> res;

        for (const string& word : words) {
            bool found = false;
            for (int r = 0; r < ROWS && !found; r++) {
                for (int c = 0; c < COLS && !found; c++) {
                    if (board[r][c] == word[0]) {
                        vector<vector<bool>> visited(ROWS, vector<bool>(COLS, false));
                        if (backtrack(r, c, word, 0, visited)) {
                            res.push_back(word);
                            found = true;
                        }
                    }
                }
            }
        }
        return res;
    }
};

// Example usage
int main() {
    vector<vector<char>> board = {
        {'o','a','a','n'},
        {'e','t','a','e'},
        {'i','h','k','r'},
        {'i','f','l','v'}
    };
    vector<string> words = {"oath","pea","eat","rain"};
    Solution sol;
    vector<string> result = sol.findWords(board, words);
    for (const string& w : result) {
        cout << w << " ";
    }
    cout << endl;
    return 0;
}

Line Notes

bool backtrack(int r, int c, const string& word, int index, vector<vector<bool>>& visited)Recursive function exploring board for current word index, checking boundaries and visited cells.

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

if (visited[r][c] || board[r][c] != word[index]) return false;Prune invalid or revisited cells to avoid wrong paths.

visited[r][c] = true;Mark cell visited before recursion to avoid reuse.

visited[r][c] = false;Unmark cell after recursion to backtrack and allow other paths.

for (const string& word : words)Iterate over all words independently to find each separately.

if (board[r][c] == word[0])Start backtracking from cells matching the first letter of the word.

var findWords = function(board, words) {
    const ROWS = board.length, COLS = board[0].length;
    const res = [];

    function backtrack(r, c, word, index, visited) {
        if (index === word.length) return true;
        if (r < 0 || c < 0 || r >= ROWS || c >= COLS) return false;
        if (visited.has(r + ',' + c) || board[r][c] !== word[index]) return false;

        visited.add(r + ',' + c);
        const found = backtrack(r+1, c, word, index+1, visited) ||
                      backtrack(r-1, c, word, index+1, visited) ||
                      backtrack(r, c+1, word, index+1, visited) ||
                      backtrack(r, c-1, word, index+1, visited);
        visited.delete(r + ',' + c);
        return found;
    }

    for (const word of words) {
        let foundWord = false;
        for (let r = 0; r < ROWS && !foundWord; r++) {
            for (let c = 0; c < COLS && !foundWord; c++) {
                if (board[r][c] === word[0]) {
                    if (backtrack(r, c, word, 0, new Set())) {
                        res.push(word);
                        foundWord = true;
                    }
                }
            }
        }
    }
    return res;
};

// Example usage
const board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
];
const words = ["oath","pea","eat","rain"];
console.log(findWords(board, words));

Line Notes

function backtrack(r, c, word, index, visited)Recursive helper to explore board for current word index, checking boundaries and visited cells.

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

if (visited.has(r + ',' + c) || board[r][c] !== word[index]) return false;Prune invalid or revisited cells to avoid wrong paths.

visited.add(r + ',' + c);Mark cell visited before recursion to avoid reuse.

visited.delete(r + ',' + c);Unmark cell after recursion to backtrack and allow other paths.

for (const word of words)Iterate over all words independently to find each separately.

if (board[r][c] === word[0])Start backtracking from cells matching the first letter of the word.

⏱

Complexity

TimeO(W * N * M * 4^L) where N and M are board dimensions, L is max word length, W is number of words

SpaceO(L) recursion stack + O(L) visited set per search

For each word, we scan the board and do a DFS that can explore up to 4 directions per letter, leading to exponential time in word length. Doing this for all words multiplies by W.

💡 For a 12x12 board and 10-letter words, this approach tries billions of paths per word, making it impractical for large word lists.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and correctness before optimizing.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(W * N * M * 4^L)`	`O(L) recursion + O(L) visited set`	Yes (deep recursion for long words)	N/A	Mention only - never code due to inefficiency
2. Backtracking with Trie	`O(N * M * 4^L)`	`O(W * L) trie + O(L) recursion`	Yes	N/A	Code this for efficient solution
3. Backtracking with Trie and In-Place Marking	`O(N * M * 4^L)`	`O(W * L) trie, no extra visited set`	Yes	N/A	Code this if asked for space optimization

Practice

(1/5)

1. Given a binary tree where each node contains an integer value, you need to find the maximum sum of values along any path. The path can start and end at any node, and must be continuous (parent-child connections). Which approach guarantees finding the optimal maximum path sum efficiently?

easy

A. Use a recursive postorder traversal that computes maximum gains from children and updates a global max path sum including both children at each node.

B. Use a greedy traversal that picks the maximum child sum at each node without backtracking.

C. Use a breadth-first search to accumulate sums level by level and pick the maximum sum found.

D. Use dynamic programming on node values treating the tree as a linear array and summing consecutive nodes.

3. Consider the following buggy LFUCache code snippet. Which line contains the subtle bug that causes incorrect eviction behavior?

def put(self, key: int, value: int) -> None:
    if self.capacity == 0:
        return
    self.time += 1
    if key in self.cache:
        _, freq, _ = self.cache[key]
        self.cache[key] = (value, freq + 1, self.time)
        return
    if len(self.cache) == self.capacity:
        min_freq = min(freq for _, freq, _ in self.cache.values())
        lfu_keys = [k for k, (_, freq, _) in self.cache.items() if freq == min_freq]
        lru_key = min(lfu_keys, key=lambda k: self.cache[k][2])
        del self.cache[lru_key]
    self.cache[key] = (value, 1, self.time)

medium

A. Missing update of minimum frequency after eviction

B. Line: self.cache[key] = (value, freq + 1, self.time) when key exists

C. Line: min_freq = min(freq for _, freq, _ in self.cache.values())

D. Line: self.time += 1

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: Understand the problem requires paths that can bend at any node, including both children.

Step 2: Recognize that a recursive postorder traversal can compute max gains from left and right subtrees, and update a global max including both children plus current node.

Final Answer:

Quick Check:

Solution

Step 1: Understand brute force limitations

Step 2: Recognize Trie-based optimization

Final Answer:

Quick Check:

Solution

Step 1: Identify eviction and frequency update

Step 2: Understand impact of missing minFreq update

Final Answer:

Quick Check:

Solution

Step 1: Analyze sorting and offline queries

Step 2: Analyze trie operations

Final Answer:

Quick Check:

Solution

Step 1: Understand reuse impact

Step 2: Identify suitable approach

Final Answer:

Quick Check:

Ready to prove it?