void bfsGrid(int[][] grid, int sr, int sc) {
int rows = grid.length, cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
visited[sr][sc] = true;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{sr, sc});
int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d : dirs) {
int nr = cell[0]+d[0], nc = cell[1]+d[1];
if (nr >= 0 && nr < rows && nc >= 0
&& nc < cols && !visited[nr][nc]) {
visited[nr][nc] = true;
queue.add(new int[]{nr, nc});
}
}
}
} func bfsGrid(grid [][]int, sr, sc int) {
rows, cols := len(grid), len(grid[0])
visited := map[[2]int]bool{{sr, sc}: true}
queue := [][2]int{{sr, sc}}
dirs := [][2]int{{0,1},{1,0},{0,-1},{-1,0}}
for len(queue) > 0 {
r, c := queue[0][0], queue[0][1]
queue = queue[1:]
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < rows && nc >= 0 &&
nc < cols && !visited[[2]int{nr, nc}] {
visited[[2]int{nr, nc}] = true
queue = append(queue, [2]int{nr, nc})
}
}
}
} def bfs_grid(grid, sr, sc):
rows, cols = len(grid), len(grid[0])
visited = set()
visited.add((sr, sc))
queue = deque([(sr, sc)])
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while queue:
r, c = queue.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
visited.add((nr, nc))
queue.append((nr, nc)) fn bfs_grid(grid: &[Vec<i32>], sr: usize, sc: usize) {
let (rows, cols) = (grid.len(), grid[0].len());
let mut visited = vec![vec![false; cols]; rows];
visited[sr][sc] = true;
let mut queue = VecDeque::from([(sr, sc)]);
let dirs: [(i32, i32); 4] = [(0,1),(1,0),(0,-1),(-1,0)];
while let Some((r, c)) = queue.pop_front() {
for (dr, dc) in &dirs {
let (nr, nc) = (r as i32 + dr, c as i32 + dc);
if nr >= 0 && nr < rows as i32
&& nc >= 0 && nc < cols as i32 {
let (nr, nc) = (nr as usize, nc as usize);
if !visited[nr][nc] {
visited[nr][nc] = true;
queue.push_back((nr, nc));
}
}
}
}
} function bfsGrid(grid: number[][], sr: number, sc: number): void {
const [rows, cols] = [grid.length, grid[0].length];
const visited = new Set<string>();
visited.add(sr + "," + sc);
const queue: [number, number][] = [[sr, sc]];
const dirs = [[0,1],[1,0],[0,-1],[-1,0]];
while (queue.length) {
const [r, c] = queue.shift()!;
for (const [dr, dc] of dirs) {
const [nr, nc] = [r + dr, c + dc];
const key = nr + "," + nc;
if (nr >= 0 && nr < rows && nc >= 0
&& nc < cols && !visited.has(key)) {
visited.add(key);
queue.push([nr, nc]);
}
}
}
} 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}};
// 4-directional dirs := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}} // 8-directional dirs8 := [][2]int{ {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }
# 4-directional dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 8-directional dirs8 = [(0,1),(0,-1),(1,0),(-1,0), (1,1),(1,-1),(-1,1),(-1,-1)]
// 4-directional let dirs: [(i32, i32); 4] = [(0, 1), (0, -1), (1, 0), (-1, 0)]; // 8-directional let dirs8: [(i32, i32); 8] = [ (0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1), ];
// 4-directional const dirs: number[][] = [[0,1], [0,-1], [1,0], [-1,0]]; // 8-directional const dirs8: number[][] = [[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]); }
var dirs = [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}} func dfs(grid [][]int, r, c int) { // 1. Bounds check if r < 0 || r >= len(grid) || c < 0 || c >= len(grid[0]) { 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 _, d := range dirs { dfs(grid, r+d[0], c+d[1]) } }
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)] def dfs(grid: list[list[int]], r: int, c: int) -> None: # 1. Bounds check if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]): 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 dr, dc in dirs: dfs(grid, r + dr, c + dc)
fn dfs(grid: &mut Vec<Vec<i32>>, r: i32, c: i32) { let m = grid.len() as i32; let n = grid[0].len() as i32; // 1. Bounds check if r < 0 || r >= m || c < 0 || c >= n { return; } // 2. Validity check (skip water/visited) if grid[r as usize][c as usize] != 1 { return; } // 3. Mark visited grid[r as usize][c as usize] = 0; // 4. Recurse on all neighbors let dirs: [(i32, i32); 4] = [(0, 1), (0, -1), (1, 0), (-1, 0)]; for (dr, dc) in dirs { dfs(grid, r + dr, c + dc); } }
const dirs = [[0,1],[0,-1],[1,0],[-1,0]]; function dfs(grid: number[][], r: number, c: number): void { // 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 (const [dr, dc] of dirs) dfs(grid, r + dr, c + dc); }
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; }
func numIslands(grid [][]byte) int { count := 0 for r := 0; r < len(grid); r++ { for c := 0; c < len(grid[0]); c++ { if grid[r][c] == '1' { count++ dfsIslands(grid, r, c) // sink the island } } } return count } func dfsIslands(grid [][]byte, r, c int) { if r < 0 || r >= len(grid) || c < 0 || c >= len(grid[0]) || grid[r][c] != '1' { return } grid[r][c] = '0' dirs := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}} for _, d := range dirs { dfsIslands(grid, r+d[0], c+d[1]) } }
def num_islands(grid: list[list[str]]) -> int: count = 0 for r in range(len(grid)): for c in range(len(grid[0])): if grid[r][c] == "1": count += 1 dfs(grid, r, c) # sink the island return count
impl Solution { pub fn num_islands(grid: mut Vec<Vec<u8>>) -> i32 { let mut count = 0; let m = grid.len(); let n = grid[0].len(); for r in 0..m { for c in 0..n { if grid[r][c] == b'1' { count += 1; Solution::dfs_islands(&mut grid, r as i32, c as i32); } } } count } fn dfs_islands(grid: &mut Vec<Vec<u8>>, r: i32, c: i32) { let m = grid.len() as i32; let n = grid[0].len() as i32; if r < 0 || r >= m || c < 0 || c >= n { return; } if grid[r as usize][c as usize] != b'1' { return; } grid[r as usize][c as usize] = b'0'; // sink for (dr, dc) in [(0i32, 1i32), (0, -1), (1, 0), (-1, 0)] { Solution::dfs_islands(grid, r + dr, c + dc); } } }
function numIslands(grid: string[][]): number { let count = 0; for (let r = 0; r < grid.length; r++) { for (let 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 }
func bfs(grid [][]int, sr, sc, er, ec int) int { m, n := len(grid), len(grid[0]) dirs := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}} visited := make([][]bool, m) for i := range visited { visited[i] = make([]bool, n) } type cell struct{ r, c int } queue := []cell{{sr, sc}} visited[sr][sc] = true steps := 0 for len(queue) > 0 { size := len(queue) for i := 0; i < size; i++ { cur := queue[i] if cur.r == er && cur.c == ec { return steps // found shortest path! } for _, d := range dirs { nr, nc := cur.r+d[0], cur.c+d[1] if nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] == 0 { visited[nr][nc] = true queue = append(queue, cell{nr, nc}) } } } queue = queue[size:] steps++ } return -1 // no path found }
from collections import deque def bfs(grid: list[list[int]], sr: int, sc: int, er: int, ec: int) -> int: m, n = len(grid), len(grid[0]) dirs = [(0,1),(0,-1),(1,0),(-1,0)] visited = [[False] * n for _ in range(m)] queue: deque[tuple[int, int]] = deque([(sr, sc)]) visited[sr][sc] = True steps = 0 while queue: for _ in range(len(queue)): row, col = queue.popleft() if row == er and col == ec: return steps # found shortest path! for dr, dc in dirs: nr, nc = row + dr, col + dc if (0 <= nr < m and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 0): visited[nr][nc] = True queue.append((nr, nc)) steps += 1 return -1 # no path found
use std::collections::VecDeque; fn bfs(grid: &Vec<Vec<i32>>, sr: usize, sc: usize, er: usize, ec: usize) -> i32 { let m = grid.len(); let n = grid[0].len(); let dirs: [(i32, i32); 4] = [(0, 1), (0, -1), (1, 0), (-1, 0)]; let mut visited = vec![vec![false; n]; m]; let mut queue: VecDeque<(usize, usize)> = VecDeque::new(); queue.push_back((sr, sc)); visited[sr][sc] = true; let mut steps = 0; while !queue.is_empty() { let size = queue.len(); for _ in 0..size { let (r, c) = queue.pop_front().unwrap(); if r == er && c == ec { return steps; // found shortest path! } for &(dr, dc) in &dirs { let nr = r as i32 + dr; let nc = c as i32 + dc; if nr >= 0 && nr < m as i32 && nc >= 0 && nc < n as i32 { let (nr, nc) = (nr as usize, nc as usize); if !visited[nr][nc] && grid[nr][nc] == 0 { visited[nr][nc] = true; queue.push_back((nr, nc)); } } } } steps += 1; } -1 // no path found }
function bfs(grid: number[][], sr: number, sc: number, er: number, ec: number): number { const m = grid.length, n = grid[0].length; const dirs = [[0,1],[0,-1],[1,0],[-1,0]]; const visited: boolean[][] = Array.from({length: m}, () => new Array(n).fill(false)); const queue: [number, number][] = [[sr, sc]]; visited[sr][sc] = true; let steps = 0; while (queue.length > 0) { const size = queue.length; for (let i = 0; i < size; i++) { const [row, col] = queue.shift()!; if (row === er && col === ec) return steps; // found shortest path! for (const [dr, dc] of dirs) { const nr = row + dr, nc = col + dc; if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] === 0) { visited[nr][nc] = true; queue.push([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; }
func spiralOrder(matrix [][]int) []int { result := []int{} top, bottom := 0, len(matrix)-1 left, right := 0, len(matrix[0])-1 for top <= bottom && left <= right { // Traverse right along top row for c := left; c <= right; c++ { result = append(result, matrix[top][c]) } top++ // Traverse down along right column for r := top; r <= bottom; r++ { result = append(result, matrix[r][right]) } right-- // Traverse left along bottom row if top <= bottom { for c := right; c >= left; c-- { result = append(result, matrix[bottom][c]) } bottom-- } // Traverse up along left column if left <= right { for r := bottom; r >= top; r-- { result = append(result, matrix[r][left]) } left++ } } return result }
def spiral_order(matrix: list[list[int]]) -> list[int]: result: list[int] = [] top, bottom = 0, len(matrix) - 1 left, right = 0, len(matrix[0]) - 1 while top <= bottom and left <= right: # Traverse right along top row for c in range(left, right + 1): result.append(matrix[top][c]) top += 1 # Traverse down along right column for r in range(top, bottom + 1): result.append(matrix[r][right]) right -= 1 # Traverse left along bottom row if top <= bottom: for c in range(right, left - 1, -1): result.append(matrix[bottom][c]) bottom -= 1 # Traverse up along left column if left <= right: for r in range(bottom, top - 1, -1): result.append(matrix[r][left]) left += 1 return result
impl Solution { pub fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> { let mut result = Vec::new(); if matrix.is_empty() { return result; } let (mut top, mut bottom) = (0i32, matrix.len() as i32 - 1); let (mut left, mut right) = (0i32, matrix[0].len() as i32 - 1); while top <= bottom && left <= right { // Traverse right along top row for c in left..=right { result.push(matrix[top as usize][c as usize]); } top += 1; // Traverse down along right column for r in top..=bottom { result.push(matrix[r as usize][right as usize]); } right -= 1; // Traverse left along bottom row if top <= bottom { for c in (left..=right).rev() { result.push(matrix[bottom as usize][c as usize]); } bottom -= 1; } // Traverse up along left column if left <= right { for r in (top..=bottom).rev() { result.push(matrix[r as usize][left as usize]); } left += 1; } } result } }
function spiralOrder(matrix: number[][]): number[] { const result: number[] = []; let top = 0, bottom = matrix.length - 1; let left = 0, right = matrix[0].length - 1; while (top <= bottom && left <= right) { // Traverse right along top row for (let c = left; c <= right; c++) result.push(matrix[top][c]); top++; // Traverse down along right column for (let r = top; r <= bottom; r++) result.push(matrix[r][right]); right--; // Traverse left along bottom row if (top <= bottom) { for (let c = right; c >= left; c--) result.push(matrix[bottom][c]); bottom--; } // Traverse up along left column if (left <= right) { for (let r = bottom; r >= top; r--) result.push(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.