Word Search in Java: Find All Occurrences in a Grid

Introduction

Searching for a word inside a 2D character matrix is a common matrix and grid-based interview problem. The challenge becomes more interesting when the word can be formed in any of the 8 directions, including horizontal, vertical, and diagonal directions.

In this article, we will solve the Word in Grid – All Occurrences problem in Java and understand the directional traversal technique, why DFS is not required, and how to achieve the expected time and space complexity.

Problem Statement

Given a 2D character matrix mat[][] and a string word, find all starting positions where the given word occurs in the matrix.

The word can be formed by moving in any of the 8 directions:

Left
Right
Up
Down
Top-left diagonal
Top-right diagonal
Bottom-left diagonal
Bottom-right diagonal

The movement must remain in the same direction throughout an occurrence.

Each cell can be used at most once for an occurrence, and the result should contain unique starting coordinates in lexicographically smallest order.

Example

Consider the following matrix:

a b a b
a b e b
e b e b

and:

word = "abe"

The word can be found starting at:

(0,0)
(0,2)
(1,0)

Therefore, the expected output is:

[[0,0], [0,2], [1,0]]

For example, starting from (0,0), the word is found diagonally:

(0,0) → a
(1,1) → b
(2,2) → e

Key Observation

The most important observation is that the word must be formed in a straight line.

Once we choose a direction, we do not change direction while matching the remaining characters.

There are exactly eight possible directions:

↖  ↑  ↗
←     →
↙  ↓  ↘

Instead of writing separate logic for each direction, we can represent the row and column movement using two arrays:

int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};

Here:

dr represents the change in the row.
dc represents the change in the column.

For example:

dr = -1
dc =  0

means move one row upward.

Similarly:

dr = 1
dc = 1

means move diagonally down-right.

Approach

We can solve the problem using the following steps.

Step 1: Traverse Every Cell

Use two nested loops to consider every matrix cell as a potential starting position.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        // Check this cell
    }
}

Step 2: Check the First Character

There is no reason to search from a cell if it does not contain the first character of the word.

if (mat[i][j] != word.charAt(0)) {
    continue;
}

For example, if:

word = "abe"

we only need to start searching from cells containing a.

Step 3: Try All Eight Directions

For every valid starting cell, check all eight possible directions.

for (int d = 0; d < 8; d++) {
    // Check this direction
}

The variable d represents the current direction.

Step 4: Move Through the Matrix

Initially, the current position is the starting cell:

int r = i;
int c = j;

For every subsequent character, move using the selected direction:

r += dr[d];
c += dc[d];

Because the same d is used for every step, the search continues in a straight line.

Step 5: Check the Boundaries

Before accessing the matrix, verify that the position is inside the grid:

if (r < 0 || r >= n || c < 0 || c >= m) {
    break;
}

This prevents an ArrayIndexOutOfBoundsException.

Step 6: Compare Characters

The character at the current matrix position must match the corresponding character in the word.

if (mat[r][c] != word.charAt(k)) {
    break;
}

If the character does not match, that direction cannot form the word.

Step 7: Store the Starting Position

If all characters have been matched, the word has been found.

The required result is the starting coordinate, so we store (i, j):

ArrayList<Integer> position = new ArrayList<>();
position.add(i);
position.add(j);
result.add(position);

Complete Java Solution

import java.util.ArrayList;

class Solution {
    public ArrayList<ArrayList<Integer>> searchWord(
            char[][] mat, String word) {

        ArrayList<ArrayList<Integer>> result =
                new ArrayList<>();

        int n = mat.length;
        int m = mat[0].length;

        // 8 possible directions
        int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};

        // Traverse every cell
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {

                // First character must match
                if (mat[i][j] != word.charAt(0)) {
                    continue;
                }

                // Try all 8 directions
                for (int d = 0; d < 8; d++) {

                    int r = i;
                    int c = j;
                    int k;

                    // Check remaining characters
                    for (k = 1; k < word.length(); k++) {

                        r += dr[d];
                        c += dc[d];

                        // Check boundary
                        if (r < 0 || r >= n || c < 0 || c >= m) {
                            break;
                        }

                        // Character mismatch
                        if (mat[r][c] != word.charAt(k)) {
                            break;
                        }
                    }

                    // Complete word found
                    if (k == word.length()) {

                        ArrayList<Integer> position =
                                new ArrayList<>();

                        position.add(i);
                        position.add(j);

                        result.add(position);

                        // Avoid duplicate starting position
                        break;
                    }
                }
            }
        }

        return result;
    }
}

Understanding the Direction Arrays

The following arrays are the heart of the solution:

int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};

They represent the eight possible movements:

Direction	`dr`	`dc`
Top-left ↖	-1	-1
Up ↑	-1	0
Top-right ↗	-1	1
Left ←	0	-1
Right →	0	1
Bottom-left ↙	1	-1
Down ↓	1	0
Bottom-right ↘	1	1

This technique avoids writing eight separate search implementations.

For example, bottom-right is represented by:

dr = 1
dc = 1

Starting from (i, j), the positions become:

(i, j)
(i + 1, j + 1)
(i + 2, j + 2)
(i + 3, j + 3)
...

Dry Run

Consider the following matrix:

a b a b
a b e b
e b e b

and:

word = "abe"

Starting at `(0,0)`

The first character is a, so we begin searching.

Try the bottom-right direction:

(0,0) → a
(1,1) → b
(2,2) → e

All three characters match:

a
  b
    e

Therefore, add:

[0,0]

Starting at `(0,2)`

Again, the first character is a.

Try the bottom-left direction:

(0,2) → a
(1,1) → b
(2,0) → e

The word is found, so add:

[0,2]

Starting at `(1,0)`

Try the right direction:

(1,0) → a
(1,1) → b
(1,2) → e

The word is found, so add:

[1,0]

The final result is:

[[0,0], [0,2], [1,0]]

Why Don't We Need DFS?

Although this is a matrix and grid problem that may appear under DFS-related topics, a full recursive DFS is not necessary for this particular problem.

The reason is that the word must be formed in a single straight direction.

Once a direction is selected, the next position is completely determined.

For example, after selecting bottom-right, the search must follow:

(i, j)
(i + 1, j + 1)
(i + 2, j + 2)
(i + 3, j + 3)

There is no branching to other neighboring cells.

In a traditional word-search problem where movement can change direction at every step, DFS is useful because every cell can lead to multiple possible paths.

Here, that branching does not exist.

Therefore, a simple iterative directional traversal is sufficient.

Why Don't We Need a Visited Array?

Many grid-based word-search problems require a visited[][] array because a search can move between different neighboring cells and must prevent a cell from being reused.

This problem is different because movement remains in one fixed direction.

For a word with length greater than one, every step moves to the next cell along that direction. Therefore, the same cell cannot be revisited during the same straight-line search.

As a result, we do not need:

boolean[][] visited;

This allows the algorithm to use constant auxiliary space.

Handling Duplicate Starting Positions

The result requires unique starting coordinates.

It is possible for the same starting cell to form the word in more than one direction.

For example, a word might exist both horizontally and diagonally from the same starting position.

Once a word is found from a particular starting cell, we execute:

break;

This exits the direction loop.

Therefore, the starting coordinate is added only once.

The relevant part of the solution is:

if (k == word.length()) {

    ArrayList<Integer> position =
            new ArrayList<>();

    position.add(i);
    position.add(j);

    result.add(position);

    break;
}

Lexicographical Order

The result needs to be returned in lexicographically smallest order.

We traverse the matrix from the top-left corner toward the bottom-right corner:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        // ...
    }
}

Therefore, coordinates are encountered in this order:

(0,0)
(0,1)
(0,2)
...
(1,0)
(1,1)
...

This is already lexicographical order for the coordinate pairs.

As a result, no additional sorting is required.

Complexity Analysis

Let:

n = number of rows
m = number of columns
k = length of the word

For every cell, we check up to 8 directions. For each direction, we can inspect up to k characters.

Therefore:

O(n × m × 8 × k)

Since 8 is a constant:

Time Complexity = O(n × m × k)

The algorithm uses only the two direction arrays and a few variables.

Therefore:

Auxiliary Space = O(1)

This excludes the space required to store the output coordinates.

Important Interview Points

Why Are There Eight Directions?

Movement is allowed horizontally, vertically, and diagonally.

There are:

3 directions above
2 horizontal directions
3 directions below

Therefore:

3 + 2 + 3 = 8

Why Use Direction Arrays?

Instead of writing separate logic for every direction, we represent each movement using dr[] and dc[].

This makes the implementation shorter and reduces repetitive code.

Why Is Recursion Not Required?

After selecting a direction, the next cell is predetermined. There is no branching, so iterative traversal is sufficient.

Why Is a Visited Array Not Required?

The search remains in one fixed direction, so the same cell cannot be revisited during one straight-line occurrence.

Why Don't We Need to Sort the Result?

The matrix is traversed from top-left to bottom-right, so valid starting coordinates are naturally generated in lexicographical order.

Common Mistakes

Mistake 1: Checking Only Four Directions

A common implementation checks only:

Up
Down
Left
Right

That is insufficient because diagonal movement is also allowed.

All eight directions must be checked.

Mistake 2: Changing Direction

The word must be formed in a straight line.

This is invalid:

Right → Down → Right

A valid occurrence looks like:

Right → Right → Right

or:

Down-right → Down-right → Down-right

Mistake 3: Returning the Ending Coordinate

The problem asks for the starting coordinate.

Therefore, store:

i, j

rather than:

r, c

Mistake 4: Forgetting Boundary Checks

Before accessing:

mat[r][c]

always verify:

r >= 0
r < n
c >= 0
c < m

Otherwise, the application can throw an ArrayIndexOutOfBoundsException.

Final Takeaway

The key idea behind this problem is straightforward:

For every cell
    ↓
Check the first character
    ↓
Try all 8 directions
    ↓
Move in the selected direction
    ↓
Compare the remaining characters
    ↓
If the complete word matches
    ↓
Store the starting coordinate

The most important technique is the eight-direction representation:

int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};

Because the word must be formed in a straight line, a full DFS and visited[][] matrix are unnecessary.

The resulting complexity is:

Time  : O(n × m × k)
Space : O(1)

This directional traversal pattern is useful beyond this specific problem and can be applied to many matrix and grid-search problems where movement is constrained to fixed directions.

Introduction

Problem Statement

Example

Key Observation

Approach

Step 1: Traverse Every Cell

Step 2: Check the First Character

Step 3: Try All Eight Directions

Step 4: Move Through the Matrix

Step 5: Check the Boundaries

Step 6: Compare Characters

Step 7: Store the Starting Position

Complete Java Solution

Understanding the Direction Arrays

Dry Run

Starting at (0,0)

Starting at (0,2)

Starting at (1,0)

Why Don't We Need DFS?

Why Don't We Need a Visited Array?

Handling Duplicate Starting Positions

Lexicographical Order

Complexity Analysis

Important Interview Points

Why Are There Eight Directions?

Why Use Direction Arrays?

Why Is Recursion Not Required?

Why Is a Visited Array Not Required?

Why Don't We Need to Sort the Result?

Common Mistakes

Mistake 1: Checking Only Four Directions

Mistake 2: Changing Direction

Mistake 3: Returning the Ending Coordinate

Mistake 4: Forgetting Boundary Checks

Final Takeaway

Starting at `(0,0)`

Starting at `(0,2)`

Starting at `(1,0)`