The Aha Moment: Every Cell Is a Node
If you’ve ever felt stuck staring at a grid problem, unsure where to start, you’re not alone. The breakthrough comes when you realize: a matrix is just a graph in disguise.
Each cell in a 2D array is a node. The connections between adjacent cells (up, down, left, right, and sometimes diagonals) are the edges. Once this clicks, an entire category of problems becomes approachable using familiar graph algorithms.
Let’s build this mental model step by step, with practical examples in JavaScript and Go.
The Foundation: Reframing the Problem
Consider this simple 3x3 matrix:
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
As a graph, cell (0,0) containing value 1 has edges to:
- (0,1) - right neighbor (value 2)
- (1,0) - bottom neighbor (value 4)
Cell (1,1) containing value 5 is more interesting:
- (0,1) - top neighbor (value 2)
- (1,0) - left neighbor (value 4)
- (1,2) - right neighbor (value 6)
- (2,1) - bottom neighbor (value 8)
Key insight: Instead of thinking “I need to process this grid,” think “I need to traverse this graph where nodes are cells and edges connect adjacent cells.”
The Direction Vectors Pattern
Almost every matrix-as-graph problem uses this pattern:
JavaScript:
// 4-directional movement (up, down, left, right)
const directions = [
[-1, 0], // up
[1, 0], // down
[0, -1], // left
[0, 1] // right
];
// 8-directional movement (including diagonals)
const directions8 = [
[-1, -1], [-1, 0], [-1, 1],
[0, -1], [0, 1],
[1, -1], [1, 0], [1, 1]
];
function isValid(row, col, rows, cols) {
return row >= 0 && row < rows && col >= 0 && col < cols;
}
Go:
type Point struct {
row, col int
}
// 4-directional movement
var directions = []Point{
{-1, 0}, // up
{1, 0}, // down
{0, -1}, // left
{0, 1}, // right
}
// 8-directional movement
var directions8 = []Point{
{-1, -1}, {-1, 0}, {-1, 1},
{0, -1}, {0, 1},
{1, -1}, {1, 0}, {1, 1},
}
func isValid(row, col, rows, cols int) bool {
return row >= 0 && row < rows && col >= 0 && col < cols
}
This pattern appears in 90% of grid problems. Memorize it.
BFS on a Grid: Shortest Path in Unweighted Graphs
When to use: Finding shortest path in a grid where each move has equal cost (distance 1).
Problem: Find the shortest path from top-left to bottom-right in a grid.
JavaScript:
function shortestPathBFS(grid) {
const rows = grid.length;
const cols = grid[0].length;
// Start from (0,0), end at (rows-1, cols-1)
const queue = [[0, 0, 1]]; // [row, col, distance]
const visited = new Set();
visited.add('0,0');
const directions = [[-1,0], [1,0], [0,-1], [0,1]];
while (queue.length > 0) {
const [row, col, dist] = queue.shift();
// Reached destination
if (row === rows - 1 && col === cols - 1) {
return dist;
}
// Explore neighbors
for (const [dr, dc] of directions) {
const newRow = row + dr;
const newCol = col + dc;
const key = `${newRow},${newCol}`;
if (newRow >= 0 && newRow < rows &&
newCol >= 0 && newCol < cols &&
grid[newRow][newCol] !== 1 && // 1 represents obstacle
!visited.has(key)) {
visited.add(key);
queue.push([newRow, newCol, dist + 1]);
}
}
}
return -1; // No path found
}
// Example usage
const grid = [
[0, 0, 0],
[1, 1, 0],
[0, 0, 0]
];
console.log(shortestPathBFS(grid)); // Output: 5
Go:
package main
import "fmt"
type QueueItem struct {
row, col, dist int
}
func shortestPathBFS(grid [][]int) int {
rows := len(grid)
cols := len(grid[0])
queue := []QueueItem{{0, 0, 1}}
visited := make(map[string]bool)
visited["0,0"] = true
directions := [][]int{{-1,0}, {1,0}, {0,-1}, {0,1}}
for len(queue) > 0 {
curr := queue[0]
queue = queue[1:]
// Reached destination
if curr.row == rows-1 && curr.col == cols-1 {
return curr.dist
}
// Explore neighbors
for _, dir := range directions {
newRow := curr.row + dir[0]
newCol := curr.col + dir[1]
key := fmt.Sprintf("%d,%d", newRow, newCol)
if newRow >= 0 && newRow < rows &&
newCol >= 0 && newCol < cols &&
grid[newRow][newCol] != 1 && // 1 represents obstacle
!visited[key] {
visited[key] = true
queue = append(queue, QueueItem{newRow, newCol, curr.dist + 1})
}
}
}
return -1 // No path found
}
func main() {
grid := [][]int{
{0, 0, 0},
{1, 1, 0},
{0, 0, 0},
}
fmt.Println(shortestPathBFS(grid)) // Output: 5
}
Why BFS? In an unweighted graph (each edge has the same cost), BFS guarantees the shortest path because it explores nodes level by level.
DFS on a Grid: Connectivity and Exploration
When to use: Exploring all reachable cells, finding connected components, path existence (not necessarily shortest).
Problem: Can we reach the bottom-right from top-left?
JavaScript:
function canReachDFS(grid) {
const rows = grid.length;
const cols = grid[0].length;
const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
function dfs(row, col) {
// Base cases
if (row < 0 || row >= rows || col < 0 || col >= cols) {
return false;
}
if (grid[row][col] === 1 || visited[row][col]) {
return false;
}
if (row === rows - 1 && col === cols - 1) {
return true; // Reached destination
}
visited[row][col] = true;
// Try all 4 directions
const directions = [[-1,0], [1,0], [0,-1], [0,1]];
for (const [dr, dc] of directions) {
if (dfs(row + dr, col + dc)) {
return true;
}
}
return false;
}
return dfs(0, 0);
}
// Example usage
const grid = [
[0, 0, 1],
[0, 0, 0],
[1, 0, 0]
];
console.log(canReachDFS(grid)); // Output: true
Go:
package main
import "fmt"
func canReachDFS(grid [][]int) bool {
rows := len(grid)
cols := len(grid[0])
visited := make([][]bool, rows)
for i := range visited {
visited[i] = make([]bool, cols)
}
var dfs func(row, col int) bool
dfs = func(row, col int) bool {
// Base cases
if row < 0 || row >= rows || col < 0 || col >= cols {
return false
}
if grid[row][col] == 1 || visited[row][col] {
return false
}
if row == rows-1 && col == cols-1 {
return true // Reached destination
}
visited[row][col] = true
// Try all 4 directions
directions := [][]int{{-1,0}, {1,0}, {0,-1}, {0,1}}
for _, dir := range directions {
if dfs(row+dir[0], col+dir[1]) {
return true
}
}
return false
}
return dfs(0, 0)
}
func main() {
grid := [][]int{
{0, 0, 1},
{0, 0, 0},
{1, 0, 0},
}
fmt.Println(canReachDFS(grid)) // Output: true
}
DFS vs BFS: DFS uses less memory (recursion stack vs queue) but doesn’t guarantee shortest path. Use DFS when you just need to know if something exists, not the optimal way to reach it.
Flood Fill: The Paint Bucket Algorithm
Problem: Change all connected cells of the same color to a new color (like MS Paint’s bucket fill).
JavaScript:
function floodFill(image, sr, sc, newColor) {
const originalColor = image[sr][sc];
// Edge case: already the target color
if (originalColor === newColor) return image;
const rows = image.length;
const cols = image[0].length;
function fill(row, col) {
// Boundary check and color check
if (row < 0 || row >= rows || col < 0 || col >= cols) {
return;
}
if (image[row][col] !== originalColor) {
return;
}
// Fill current cell
image[row][col] = newColor;
// Fill all 4 directions
fill(row - 1, col); // up
fill(row + 1, col); // down
fill(row, col - 1); // left
fill(row, col + 1); // right
}
fill(sr, sc);
return image;
}
// Example usage
const image = [
[1, 1, 1],
[1, 1, 0],
[1, 0, 1]
];
console.log(floodFill(image, 1, 1, 2));
// Output:
// [[2, 2, 2],
// [2, 2, 0],
// [2, 0, 1]]
Go:
package main
import "fmt"
func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
originalColor := image[sr][sc]
// Edge case: already the target color
if originalColor == newColor {
return image
}
rows := len(image)
cols := len(image[0])
var fill func(row, col int)
fill = func(row, col int) {
// Boundary check and color check
if row < 0 || row >= rows || col < 0 || col >= cols {
return
}
if image[row][col] != originalColor {
return
}
// Fill current cell
image[row][col] = newColor
// Fill all 4 directions
fill(row-1, col) // up
fill(row+1, col) // down
fill(row, col-1) // left
fill(row, col+1) // right
}
fill(sr, sc)
return image
}
func main() {
image := [][]int{
{1, 1, 1},
{1, 1, 0},
{1, 0, 1},
}
result := floodFill(image, 1, 1, 2)
for _, row := range result {
fmt.Println(row)
}
// Output:
// [2 2 2]
// [2 2 0]
// [2 0 1]
}
Pattern: Flood fill is DFS starting from a seed point, visiting only cells that match a condition (same color). This pattern appears in image processing, game development (revealing mines in Minesweeper), and geographic problems.
Number of Islands: Connected Components
Problem: Count the number of islands (connected regions of 1s) in a grid where 0 is water.
JavaScript:
function numIslands(grid) {
if (!grid || grid.length === 0) return 0;
const rows = grid.length;
const cols = grid[0].length;
let count = 0;
function dfs(row, col) {
// Boundary check and water check
if (row < 0 || row >= rows || col < 0 || col >= cols ||
grid[row][col] === '0') {
return;
}
// Mark as visited by changing to '0'
grid[row][col] = '0';
// Visit all 4 directions
dfs(row - 1, col);
dfs(row + 1, col);
dfs(row, col - 1);
dfs(row, col + 1);
}
// Try starting DFS from every cell
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (grid[i][j] === '1') {
count++; // Found a new island
dfs(i, j); // Mark entire island as visited
}
}
}
return count;
}
// Example usage
const grid = [
['1', '1', '0', '0', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '1', '0', '0'],
['0', '0', '0', '1', '1']
];
console.log(numIslands(grid)); // Output: 3
Go:
package main
import "fmt"
func numIslands(grid [][]byte) int {
if len(grid) == 0 {
return 0
}
rows := len(grid)
cols := len(grid[0])
count := 0
var dfs func(row, col int)
dfs = func(row, col int) {
// Boundary check and water check
if row < 0 || row >= rows || col < 0 || col >= cols ||
grid[row][col] == '0' {
return
}
// Mark as visited by changing to '0'
grid[row][col] = '0'
// Visit all 4 directions
dfs(row-1, col)
dfs(row+1, col)
dfs(row, col-1)
dfs(row, col+1)
}
// Try starting DFS from every cell
for i := 0; i < rows; i++ {
for j := 0; j < cols; j++ {
if grid[i][j] == '1' {
count++ // Found a new island
dfs(i, j) // Mark entire island as visited
}
}
}
return count
}
func main() {
grid := [][]byte{
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'},
}
fmt.Println(numIslands(grid)) // Output: 3
}
Key insight: This is a connected components problem. Each DFS/BFS call from an unvisited land cell discovers one complete island (component). The number of times we initiate a new search equals the number of components.
Rotting Oranges: Multi-Source BFS
Problem: Fresh oranges rot if adjacent to a rotten orange. How many minutes until all oranges rot? If impossible, return -1.
JavaScript:
function orangesRotting(grid) {
const rows = grid.length;
const cols = grid[0].length;
const queue = [];
let fresh = 0;
// Find all initially rotten oranges and count fresh ones
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (grid[i][j] === 2) {
queue.push([i, j, 0]); // [row, col, time]
} else if (grid[i][j] === 1) {
fresh++;
}
}
}
// Edge case: no fresh oranges
if (fresh === 0) return 0;
const directions = [[-1,0], [1,0], [0,-1], [0,1]];
let minutes = 0;
// Multi-source BFS
while (queue.length > 0) {
const [row, col, time] = queue.shift();
minutes = Math.max(minutes, time);
for (const [dr, dc] of directions) {
const newRow = row + dr;
const newCol = col + dc;
if (newRow >= 0 && newRow < rows &&
newCol >= 0 && newCol < cols &&
grid[newRow][newCol] === 1) {
grid[newRow][newCol] = 2; // Make it rotten
fresh--;
queue.push([newRow, newCol, time + 1]);
}
}
}
return fresh === 0 ? minutes : -1;
}
// Example usage
const grid = [
[2, 1, 1],
[1, 1, 0],
[0, 1, 1]
];
console.log(orangesRotting(grid)); // Output: 4
Go:
package main
import "fmt"
type Orange struct {
row, col, time int
}
func orangesRotting(grid [][]int) int {
rows := len(grid)
cols := len(grid[0])
queue := []Orange{}
fresh := 0
// Find all initially rotten oranges and count fresh ones
for i := 0; i < rows; i++ {
for j := 0; j < cols; j++ {
if grid[i][j] == 2 {
queue = append(queue, Orange{i, j, 0})
} else if grid[i][j] == 1 {
fresh++
}
}
}
// Edge case: no fresh oranges
if fresh == 0 {
return 0
}
directions := [][]int{{-1,0}, {1,0}, {0,-1}, {0,1}}
minutes := 0
// Multi-source BFS
for len(queue) > 0 {
curr := queue[0]
queue = queue[1:]
if curr.time > minutes {
minutes = curr.time
}
for _, dir := range directions {
newRow := curr.row + dir[0]
newCol := curr.col + dir[1]
if newRow >= 0 && newRow < rows &&
newCol >= 0 && newCol < cols &&
grid[newRow][newCol] == 1 {
grid[newRow][newCol] = 2 // Make it rotten
fresh--
queue = append(queue, Orange{newRow, newCol, curr.time + 1})
}
}
}
if fresh == 0 {
return minutes
}
return -1
}
func main() {
grid := [][]int{
{2, 1, 1},
{1, 1, 0},
{0, 1, 1},
}
fmt.Println(orangesRotting(grid)) // Output: 4
}
Pattern: Multi-source BFS. Instead of starting from one source, we start from multiple sources simultaneously. This naturally gives us the minimum time to reach all reachable nodes.
Walls and Gates: Distance from Multiple Sources
Problem: Fill each empty room with its distance to the nearest gate. INF represents infinity (unreachable), 0 represents a gate, -1 represents a wall.
JavaScript:
const INF = 2147483647;
function wallsAndGates(rooms) {
if (!rooms || rooms.length === 0) return;
const rows = rooms.length;
const cols = rooms[0].length;
const queue = [];
// Find all gates and add to queue
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (rooms[i][j] === 0) {
queue.push([i, j, 0]); // [row, col, distance]
}
}
}
const directions = [[-1,0], [1,0], [0,-1], [0,1]];
// Multi-source BFS from all gates
while (queue.length > 0) {
const [row, col, dist] = queue.shift();
for (const [dr, dc] of directions) {
const newRow = row + dr;
const newCol = col + dc;
if (newRow >= 0 && newRow < rows &&
newCol >= 0 && newCol < cols &&
rooms[newRow][newCol] === INF) {
rooms[newRow][newCol] = dist + 1;
queue.push([newRow, newCol, dist + 1]);
}
}
}
}
// Example usage
const rooms = [
[INF, -1, 0, INF],
[INF, INF, INF, -1],
[INF, -1, INF, -1],
[0, -1, INF, INF]
];
wallsAndGates(rooms);
console.log(rooms);
// Output:
// [[3, -1, 0, 1],
// [2, 2, 1, -1],
// [1, -1, 2, -1],
// [0, -1, 3, 4]]
Go:
package main
import "fmt"
const INF = 2147483647
type Cell struct {
row, col, dist int
}
func wallsAndGates(rooms [][]int) {
if len(rooms) == 0 {
return
}
rows := len(rooms)
cols := len(rooms[0])
queue := []Cell{}
// Find all gates and add to queue
for i := 0; i < rows; i++ {
for j := 0; j < cols; j++ {
if rooms[i][j] == 0 {
queue = append(queue, Cell{i, j, 0})
}
}
}
directions := [][]int{{-1,0}, {1,0}, {0,-1}, {0,1}}
// Multi-source BFS from all gates
for len(queue) > 0 {
curr := queue[0]
queue = queue[1:]
for _, dir := range directions {
newRow := curr.row + dir[0]
newCol := curr.col + dir[1]
if newRow >= 0 && newRow < rows &&
newCol >= 0 && newCol < cols &&
rooms[newRow][newCol] == INF {
rooms[newRow][newCol] = curr.dist + 1
queue = append(queue, Cell{newRow, newCol, curr.dist + 1})
}
}
}
}
func main() {
rooms := [][]int{
{INF, -1, 0, INF},
{INF, INF, INF, -1},
{INF, -1, INF, -1},
{0, -1, INF, INF},
}
wallsAndGates(rooms)
for _, row := range rooms {
fmt.Println(row)
}
// Output:
// [3 -1 0 1]
// [2 2 1 -1]
// [1 -1 2 -1]
// [0 -1 3 4]
}
Key insight: This is identical to the rotting oranges problem. Multi-source BFS naturally computes the minimum distance from any source. The first time BFS reaches a cell is guaranteed to be via the shortest path.
Shortest Path with Obstacles: 0-1 BFS
Problem: Find shortest path in a grid where you can eliminate at most k obstacles.
JavaScript:
function shortestPath(grid, k) {
const rows = grid.length;
const cols = grid[0].length;
// Special case: can eliminate all obstacles
if (k >= rows + cols - 2) {
return rows + cols - 2; // Manhattan distance
}
// State: [row, col, obstacles_eliminated, distance]
const queue = [[0, 0, 0, 0]];
// visited[row][col][eliminated] = true
const visited = new Set();
visited.add('0,0,0');
const directions = [[-1,0], [1,0], [0,-1], [0,1]];
while (queue.length > 0) {
const [row, col, eliminated, dist] = queue.shift();
// Reached destination
if (row === rows - 1 && col === cols - 1) {
return dist;
}
for (const [dr, dc] of directions) {
const newRow = row + dr;
const newCol = col + dc;
if (newRow >= 0 && newRow < rows &&
newCol >= 0 && newCol < cols) {
const newEliminated = eliminated + grid[newRow][newCol];
const key = `${newRow},${newCol},${newEliminated}`;
if (newEliminated <= k && !visited.has(key)) {
visited.add(key);
queue.push([newRow, newCol, newEliminated, dist + 1]);
}
}
}
}
return -1; // No path found
}
// Example usage
const grid = [
[0, 0, 0],
[1, 1, 0],
[0, 0, 0],
[0, 1, 1],
[0, 0, 0]
];
console.log(shortestPath(grid, 1)); // Output: 6
Go:
package main
import "fmt"
type State struct {
row, col, eliminated, dist int
}
func shortestPath(grid [][]int, k int) int {
rows := len(grid)
cols := len(grid[0])
// Special case: can eliminate all obstacles
if k >= rows+cols-2 {
return rows + cols - 2 // Manhattan distance
}
queue := []State{{0, 0, 0, 0}}
visited := make(map[string]bool)
visited["0,0,0"] = true
directions := [][]int{{-1,0}, {1,0}, {0,-1}, {0,1}}
for len(queue) > 0 {
curr := queue[0]
queue = queue[1:]
// Reached destination
if curr.row == rows-1 && curr.col == cols-1 {
return curr.dist
}
for _, dir := range directions {
newRow := curr.row + dir[0]
newCol := curr.col + dir[1]
if newRow >= 0 && newRow < rows &&
newCol >= 0 && newCol < cols {
newEliminated := curr.eliminated + grid[newRow][newCol]
key := fmt.Sprintf("%d,%d,%d", newRow, newCol, newEliminated)
if newEliminated <= k && !visited[key] {
visited[key] = true
queue = append(queue, State{
row: newRow,
col: newCol,
eliminated: newEliminated,
dist: curr.dist + 1,
})
}
}
}
}
return -1 // No path found
}
func main() {
grid := [][]int{
{0, 0, 0},
{1, 1, 0},
{0, 0, 0},
{0, 1, 1},
{0, 0, 0},
}
fmt.Println(shortestPath(grid, 1)) // Output: 6
}
Advanced pattern: This extends BFS to handle weighted edges efficiently. Instead of just (row, col), our state includes additional dimensions (obstacles eliminated). This is a common pattern when the problem has multiple constraints.
Why it’s called 0-1 BFS: Edge weights are either 0 (no obstacle) or 1 (obstacle). For such graphs, we can use a deque instead of a priority queue for better performance:
Optimized JavaScript (using deque):
function shortestPathOptimized(grid, k) {
const rows = grid.length;
const cols = grid[0].length;
// Using array as deque: addFront with unshift, addBack with push
const deque = [[0, 0, 0, 0]]; // [row, col, eliminated, dist]
const visited = new Set(['0,0,0']);
const directions = [[-1,0], [1,0], [0,-1], [0,1]];
while (deque.length > 0) {
const [row, col, eliminated, dist] = deque.shift();
if (row === rows - 1 && col === cols - 1) {
return dist;
}
for (const [dr, dc] of directions) {
const newRow = row + dr;
const newCol = col + dc;
if (newRow >= 0 && newRow < rows &&
newCol >= 0 && newCol < cols) {
const obstacle = grid[newRow][newCol];
const newEliminated = eliminated + obstacle;
const key = `${newRow},${newCol},${newEliminated}`;
if (newEliminated <= k && !visited.has(key)) {
visited.add(key);
const newState = [newRow, newCol, newEliminated, dist + 1];
// If no obstacle (weight 0), add to front
// If obstacle (weight 1), add to back
if (obstacle === 0) {
deque.unshift(newState);
} else {
deque.push(newState);
}
}
}
}
}
return -1;
}
Mental Model Summary
When you see a matrix problem, ask yourself:
- Am I finding shortest path? → Use BFS
- Am I just checking connectivity/existence? → Use DFS
- Do I need to explore from multiple sources? → Multi-source BFS
- Are there different edge weights (0 and 1)? → 0-1 BFS or Dijkstra
Complexity Analysis Patterns
Space Complexity:
- DFS: O(rows × cols) for visited array + O(rows × cols) recursion stack = O(rows × cols)
- BFS: O(rows × cols) for visited + O(rows × cols) queue = O(rows × cols)
- Both are effectively the same, though BFS might use more memory in practice
Time Complexity:
- Both DFS and BFS: O(rows × cols) because we visit each cell at most once
Common Pitfalls and Tips
- Boundary checking: Always check bounds before accessing grid[row][col]
- Visited tracking: Use a Set with string keys, 2D boolean array, or modify the input (when allowed)
- Direction vectors: Memorize the 4-directional pattern
- Multi-source BFS: Add all sources to queue initially with distance 0
- State representation: For complex problems, state might include extra dimensions (obstacles eliminated, keys collected, etc.)
Practice Problems to Master This
Easy:
- Flood Fill
- Number of Islands
- Max Area of Island
Medium:
- Rotting Oranges
- Walls and Gates
- Pacific Atlantic Water Flow
- Surrounded Regions
Hard:
- Shortest Path in a Grid with Obstacles Elimination
- Escape a Large Maze
- Minimum Cost to Make at Least One Valid Path in a Grid
Conclusion
The key to mastering matrix problems is recognizing that every matrix is a graph. Once you internalize this mental model:
- Navigation becomes edge traversal
- Finding paths becomes graph search (BFS/DFS)
- Connectivity becomes connected components
- Distance becomes shortest path
With this perspective and the patterns shown above (direction vectors, BFS for shortest paths, DFS for exploration, multi-source BFS), you’ll find that most matrix problems become variations of techniques you already know.
The next time you see a grid problem, don’t think “ugh, a 2D array.” Think “aha, a graph where I know exactly what the edges are.”
Now go solve some grid problems!
Questions or feedback? I’d love to hear how this mental model helped you. Reach out at [email protected].
Happy coding!