Word Search
A medium Matrix problem included in Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Matrix
- Sheets
- 2
- Core for
- 10 roles
- Platform
- LeetCode
The problem
Given an m-by-n grid of characters and a target word, determine whether the word can be constructed by tracing adjacent cells horizontally or vertically, without reusing a cell in the same path.
Example 1
- Input
- board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
- Output
- true
Example 2
- Input
- board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
- Output
- true
Example 3
- Input
- board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
- Output
- false
- Why
- The path revisits a cell, which is not allowed.
Constraints
- m == board.length
- n == board[i].length
- 1 <= m, n <= 6
- 1 <= word.length <= 15
- board and word consist of uppercase and lowercase English letters
How to think about it
Updated 2026-09-09The board is a graph and the word defines a path through it. At each cell only neighbors matching the next character are valid moves, so the search is tightly constrained by the word itself. The visited set prevents cycles within a single path.
Approaches, worst first
Backtracking with a visited set
time O(m*n*4^L) · space O(L)
For each starting cell, depth-first search in four directions, maintaining a set of visited coordinates for the current path. The word length bounds the recursion depth. Correct but allocates a set per path branch.
Backtracking with in-place marking
time O(m*n*4^L) · space O(1)
Same search but instead of a separate set, temporarily overwrite the current cell with a sentinel value before recursing and restore it on return. The board itself remembers which cells are in the current path.
Character frequency pruningWrite this one
time O(m*n + L) · space O(1)
Before searching, count every character available on the board and compare against the word. If any character in the word is missing or appears more often than on the board, the search is impossible and can be skipped entirely.
Where people lose marks · 3
- The visited state must be scoped to the current path, not shared across different starting cells or branches. Restoring the cell value on backtrack is the standard way to achieve this without an explicit set.
- A word of length 1 still requires checking every cell on the board as a potential match. An early return that assumes the word is longer skips valid single-character matches.
- Forgetting to restore the cell value on backtrack means subsequent branches of the depth-first search see a corrupted board and miss valid paths that pass through that cell.
The theory behind it
Matrix — the ground this problem stands on. All Matrix problems
What Matrix is
A matrix is a flat grid of cells laid out in rows and columns, like a checkerboard or a spreadsheet. Each cell has an address made of two numbers: its row index going down and its column index going across. Because computer memory stores these rows one after another or as arrays of arrays, jumping straight to any individual cell takes the same tiny fraction of time no matter where it sits on the board.
When to reach for it
Reach for matrix techniques when the input is a two-dimensional grid, board, or map. Common prompts include walking through a maze, finding connected islands of land in water, rotating an image ninety degrees in place, or reading numbers in a spiral. Words like rows, columns, neighbors, adjacent squares, or diagonal lines are clear signs. It also appears in grid planning where each cell depends on the values above and to the left.
How the pattern works
Think of navigating the grid using directional coordinate offsets. Define row and column step arrays for moving up, down, left, and right. Always check that new row and column indices stay strictly between zero and the board boundaries before reading cell values. For spiral scans, track four boundary lines for top, bottom, left, and right, shrinking them inward after reading each side. When searching connected regions, mark visited cells directly or write a marker value into the cell to avoid looping.
What each operation costs
| Operation | Time |
|---|---|
| read or write cell by row and column | O(1) |
| visit every cell across m rows and n columns | O(m * n) |
| rotate square matrix in place | O(n^2) |
What usually goes wrong with Matrix
- Flipping row and column dimensions by mixing up grid height with grid width, causing index out of bounds crashes on rectangular grids where row and column counts differ.
- Reading neighbor cells without first confirming that the row and column coordinates are within valid bounds between zero and the board edges.
- Forgetting to update inner boundary limits during spiral traversal, which causes single-row or single-column matrices to print duplicate entries.
Which roles need this problem
Matrix is a core topic for these 10 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 7 more roles, including Frontend Engineer, Full-Stack Developer, Android Developer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Matrix problems
Problem set and role mapping as of .