Introduction

Graph problems usually make people immediately think about:

adjacency lists
nodes
edges
complex graph construction

But 2D grid problems follow a completely different philosophy.

In matrix traversal problems:

The matrix itself IS the graph.

Every cell behaves like a graph node.

And neighboring cells automatically become edges.

Once you understand this mental shift, a massive category of graph problems suddenly becomes much easier.

This pattern is commonly called:

Island Pattern
Matrix Traversal Pattern
Grid DFS/BFS Pattern

It appears everywhere in coding interviews.

Why Matrix Problems Are Secretly Graph Problems

Consider this grid:

Each cell can connect to neighboring cells.

That means:

cells = nodes
movements = edges

You are already working with a graph.

The difference is:

The graph is implicit.

You do not need to build it manually.

The Biggest Beginner Mistake

Many beginners try converting the matrix into:


text
Map<Integer, List<Integer>>

or some adjacency structure.

This creates:

unnecessary memory usage
extra preprocessing
slower implementations
complicated logic

In grid problems:

The matrix already stores everything you need.

Understanding Connectivity

In most island problems, movement is allowed in 4 directions:


text
        UP
         ↑
LEFT ← CELL → RIGHT
         ↓
       DOWN

This creates natural graph connectivity.

Sometimes problems also allow diagonal movement:


text
↖ ↑ ↗
← X →
↙ ↓ ↘

Understanding movement directions is the foundation of the entire pattern.

The Direction Array Trick

One of the cleanest optimizations in matrix traversal is using a direction array.

Instead of writing:


java
dfs(r - 1, c);
dfs(r + 1, c);
dfs(r, c - 1);
dfs(r, c + 1);

we store movements in a reusable structure:


java
int[][] dirs = {
    {-1, 0},
    {1, 0},
    {0, -1},
    {0, 1}
};

Now traversal becomes elegant:


java
for (int[] d : dirs) {
    dfs(r + d[0], c + d[1]);
}

This dramatically improves readability and scalability.

The Core DFS Traversal Logic

Every matrix DFS follows the same structure:

Step 1: Boundary Validation

Before exploring a cell:

ensure row is valid
ensure column is valid
ensure cell is traversable
ensure cell is not already visited

Step 2: Mark Visited

Prevent infinite recursion loops.

Step 3: Explore Neighbors

Traverse all valid neighboring cells.

That is the entire pattern.

Visual DFS Walkthrough

Consider:

Suppose we start DFS at:


text
(0,0)

Step 1

Visit:


text
1 1 0
1 0 1
0 1 1
↑

Mark visited.

Step 2

Explore neighbors:

up ❌
down ✅
left ❌
right ✅

DFS spreads recursively.

Step 3

Entire connected island becomes visited.

This is exactly how:

Number of Islands
Flood Fill
Surrounded Regions
Distinct Islands

all work internally.

Why Infinite Loops Happen

Suppose you move:


text
A → B

Without marking visited:

B again revisits A.

Then:


text
A → B → A → B → A

Recursion never ends.

That is why visited tracking is mandatory.

The Elegant Optimization: In-Place Mutation

Most beginners use:


java
boolean[][] visited

This works.

But consumes:


text
O(N × M)

extra memory.

Instead:

If the problem allows modifying input:

We can mutate the grid directly.

Example:


java
grid[r][c] = 0;

This instantly marks the node visited.

No extra matrix needed.

This is one of the cleanest space optimizations in graph traversal.

DFS vs BFS in Grid Problems

Both approaches work.

DFS (Depth First Search)

DFS explores deeply first.

Behavior:


text
Go deep → backtrack → continue

Usually implemented recursively.

Best for:

islands
component counting
shape exploration

BFS (Breadth First Search)

BFS explores level-by-level.

Behavior:


text
Explore all neighbors first

Implemented using queue.

Best for:

shortest path
minimum distance
nearest exits
rotting oranges

Complexity Analysis

Suppose grid size is:


text
N × M

Time Complexity

O(N × M)

Every cell is visited at most once.

Space Complexity

Recursive DFS

Worst case recursion stack:


text
O(N × M)

BFS Queue

Worst case:


text
O(N × M)

Auxiliary Space Optimization

If mutating grid directly:

No separate visited matrix required.

Common Matrix Traversal Problems

This exact pattern appears in:

Number of Islands
Flood Fill
Rotten Oranges
Pacific Atlantic Water Flow
Surrounded Regions
Number of Enclaves
Distinct Islands
Word Search
Shortest Path in Binary Matrix

Mastering this single pattern unlocks a massive portion of graph interviews.

Common Mistakes

Forgetting Boundary Checks

Causes:


text
ArrayIndexOutOfBoundsException

Forgetting Visited Logic

Creates infinite recursion.

Building Adjacency Lists

Usually unnecessary for matrix problems.

Rewriting Neighbor Logic Repeatedly

Direction arrays simplify everything.

The Deep Insight Behind the Pattern

The real power of matrix traversal comes from understanding:

Graphs are not always explicit.

Sometimes:

The structure itself defines the graph naturally.

Once you recognize connectivity patterns inside matrices, graph traversal becomes dramatically simpler and far more intuitive.

Final Thoughts

The Matrix Traversal Pattern is one of the most important graph concepts in technical interviews.

At first, grid problems may appear visually intimidating.

But almost all of them reduce to three simple operations:

validate
mark visited
explore neighbors

Once that recursive flow becomes natural, an enormous category of graph problems suddenly feels repetitive instead of difficult.

That is exactly when true pattern recognition begins.

Graph Patterns: The Matrix Traversal (Island) Pattern