Navigate grids with DFS, BFS, and directional movement patterns.
Matrix traversal is the art of moving through a 2D grid systematically. You treat each cell as a "node" and its neighbors as "edges", then apply graph traversal algorithms (DFS or BFS) to explore the grid.
From any cell, you can typically move in 4 or 8 directions:
Encode movement as an array of (row, col) deltas. This is the most common pattern you will see in grid problems:
// 4-directional int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}}; // 8-directional int[][] dirs8 = {{0,1},{0,-1},{1,0},{-1,0}, {1,1},{1,-1},{-1,1},{-1,-1}};
Think of the grid as a graph. Each cell is a node with up to 4 (or 8) edges to its neighbors. Once you see it this way, you can apply DFS, BFS, union-find, or any graph algorithm you already know.
If a problem gives you a 2D array and asks about connected regions, shortest paths, or reachability, it is almost certainly a matrix traversal problem:
DFS vs BFS on grids: Use DFS when you need to explore all reachable cells (islands, flood fill, connected components). Use BFS when you need the shortest path or need to process level-by-level (rotting oranges, nearest exit).
The recursive DFS template for grids is one of the most reusable patterns in competitive programming. Visit a cell, mark it as visited, then recurse on all valid neighbors.
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}}; void dfs(int[][] grid, int r, int c) { // 1. Bounds check if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return; // 2. Validity check (skip water/visited) if (grid[r][c] != 1) return; // 3. Mark visited grid[r][c] = 0; // 4. Recurse on all neighbors for (int[] d : dirs) dfs(grid, r + d[0], c + d[1]); }
Scan every cell. When you find a '1', trigger DFS to sink the entire island, then increment the count.
int numIslands(char[][] grid) { int count = 0; for (int r = 0; r < grid.length; r++) { for (int c = 0; c < grid[0].length; c++) { if (grid[r][c] == '1') { count++; dfs(grid, r, c); // sink the island } } } return count; }
In-place marking: By setting grid[r][c] = 0 we use the grid itself as the visited set, saving O(m*n) space. If you cannot modify the input, use a separate boolean[][] visited array.
When you need the shortest path in an unweighted grid, BFS is the right tool. It explores cells in order of distance, guaranteeing the first time you reach a cell is via the shortest path.
int bfs(int[][] grid, int sr, int sc, int er, int ec) { int m = grid.length, n = grid[0].length; int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}}; boolean[][] visited = new boolean[m][n]; Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{sr, sc}); visited[sr][sc] = true; int steps = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int[] cell = queue.poll(); if (cell[0] == er && cell[1] == ec) return steps; // found shortest path! for (int[] d : dirs) { int nr = cell[0] + d[0], nc = cell[1] + d[1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] == 0) { visited[nr][nc] = true; queue.offer(new int[]{nr, nc}); } } } steps++; } return -1; // no path found }
BFS explores cells in concentric rings outward from the source. Each ring represents one more step of distance:
Mark visited when enqueuing, not when dequeuing. If you wait to mark visited until you dequeue a cell, you might enqueue the same cell multiple times from different neighbors. This wastes time and memory. Always mark as visited immediately when adding to the queue.
A different kind of matrix traversal: visit cells in spiral order (right, down, left, up, repeat). The trick is maintaining four shrinking boundaries.
List<Integer> spiralOrder(int[][] matrix) { List<Integer> result = new ArrayList<>(); int top = 0, bottom = matrix.length - 1; int left = 0, right = matrix[0].length - 1; while (top <= bottom && left <= right) { // Traverse right along top row for (int c = left; c <= right; c++) result.add(matrix[top][c]); top++; // Traverse down along right column for (int r = top; r <= bottom; r++) result.add(matrix[r][right]); right--; // Traverse left along bottom row if (top <= bottom) { for (int c = right; c >= left; c--) result.add(matrix[bottom][c]); bottom--; } // Traverse up along left column if (left <= right) { for (int r = bottom; r >= top; r--) result.add(matrix[r][left]); left++; } } return result; }
The boundary guards (if (top <= bottom) and if (left <= right)) prevent double-counting when the remaining area collapses to a single row or column. Without them, you would traverse the same cells twice.
These LeetCode problems directly test matrix traversal patterns:
Click cells to toggle walls, then set a start and end point. BFS will find the shortest path with a wavefront animation. Use Step to advance one BFS level at a time, or Run All to see the full animation.
Both DFS and BFS visit each cell at most once, giving O(m * n) time where m and n are the grid dimensions. For space: DFS uses O(m * n) in the worst case for the recursion stack (imagine a spiral-shaped path), and BFS can hold up to O(m * n) cells in the queue. The visited array also takes O(m * n) space.
Spiral traversal is different: It uses O(1) extra space (just the four boundary pointers) since it reads the matrix directly without recursion or a queue. Time is still O(m*n) since every cell is visited exactly once.