- Grid as a Graph
- DFS on Grid
- BFS on Grid
- 0-1 BFS on Grid
- Dijkstra on Grid
- A* on Grid
- Flood Fill
- Connected Components
- Cycle Detection in Grid
- Matrix DP + Graph Hybrid Patterns
- Topological Sort on Grid
- Union-Find on Grid
- Grid Transformation Tricks
- Classic Problem Patterns
- Complexity Cheat Sheet
- Key Interview Q&A
A 2D grid of size M × N is just an implicit graph:
- Each cell (r, c) is a vertex — total V = M × N vertices
- Adjacent cells are connected by edges — up to 4 or 8 per cell
Grid: Graph view:
+---+---+---+ (0,0)—(0,1)—(0,2)
| 1 | 2 | 3 | | | |
+---+---+---+ (1,0)—(1,1)—(1,2)
| 4 | 5 | 6 | | | |
+---+---+---+ (2,0)—(2,1)—(2,2)
| 7 | 8 | 9 |
+---+---+---+
No need to build an explicit adjacency list — neighbors are computed on the fly.
| Concept | Grid equivalent |
|---|---|
| Vertex | Cell (r, c) |
| Edge | Moving from cell to adjacent cell |
| Edge weight | Cell value, move cost, or 1 (unweighted) |
| Visited | boolean[][] visited or in-place marking |
| BFS frontier | Queue of int[]{r, c} or encoded r * n + c |
// 4-directional (up, down, left, right) — most common
int[][] dirs4 = {{0,1},{0,-1},{1,0},{-1,0}};
// 8-directional (includes diagonals)
int[][] dirs8 = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
// Named directions for clarity
int[] DR = {-1, 1, 0, 0}; // row delta
int[] DC = { 0, 0, -1, 1}; // col delta
// 0=up, 1=down, 2=left, 3=right
// Knight moves (chess)
int[][] knight = {{-2,-1},{-2,1},{-1,-2},{-1,2},{2,-1},{2,1},{1,-2},{1,2}};// ── Core validity check ─────────────────────────────
boolean isValid(int r, int c, int m, int n) {
return r >= 0 && r < m && c >= 0 && c < n;
}
// ── 2D index to 1D (for Union-Find or visited array) ─
int encode(int r, int c, int n) { return r * n + c; }
int[] decode(int idx, int n) { return new int[]{idx / n, idx % n}; }
// ── Universal BFS skeleton ────────────────────────────
void bfsSkeleton(int[][] grid, int sr, int sc) {
int m = grid.length, n = grid[0].length;
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
visited[sr][sc] = true;
queue.offer(new int[]{sr, sc});
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
// process cell here
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (isValid(nr, nc, m, n) && !visited[nr][nc] && /* condition */) {
visited[nr][nc] = true;
queue.offer(new int[]{nr, nc});
}
}
}
}
// ── Universal DFS skeleton ────────────────────────────
void dfsSkeleton(int[][] grid, boolean[][] visited, int r, int c) {
int m = grid.length, n = grid[0].length;
visited[r][c] = true;
// process cell here
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (isValid(nr, nc, m, n) && !visited[nr][nc] && /* condition */) {
dfsSkeleton(grid, visited, nr, nc);
}
}
}class GridDFS {
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
void dfs(int[][] grid, boolean[][] visited, int r, int c) {
int m = grid.length, n = grid[0].length;
visited[r][c] = true;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& !visited[nr][nc]
&& grid[nr][nc] != 0) { // walkable condition
dfs(grid, visited, nr, nc);
}
}
}
}Avoids stack overflow on very large grids (e.g., 300×300 = 90,000 deep recursion).
void dfsIterative(int[][] grid, int sr, int sc) {
int m = grid.length, n = grid[0].length;
boolean[][] visited = new boolean[m][n];
Deque<int[]> stack = new ArrayDeque<>();
visited[sr][sc] = true;
stack.push(new int[]{sr, sc});
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!stack.isEmpty()) {
int[] cell = stack.pop();
int r = cell[0], c = cell[1];
// process cell here
System.out.println("Visiting: " + r + "," + c);
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
visited[nr][nc] = true;
stack.push(new int[]{nr, nc});
}
}
}
}Number of Islands — count connected components of '1's.
// LeetCode 200 — Number of Islands
int numIslands(char[][] grid) {
int m = grid.length, n = grid[0].length;
int count = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == '1') {
count++;
dfsIsland(grid, r, c); // sink the island
}
}
}
return count;
}
void dfsIsland(char[][] grid, int r, int c) {
int m = grid.length, n = grid[0].length;
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != '1') return;
grid[r][c] = '0'; // mark visited in-place (sink the cell)
dfsIsland(grid, r+1, c);
dfsIsland(grid, r-1, c);
dfsIsland(grid, r, c+1);
dfsIsland(grid, r, c-1);
}Max Area of Island — DFS that returns size of each island.
// LeetCode 695
int maxAreaOfIsland(int[][] grid) {
int m = grid.length, n = grid[0].length;
int maxArea = 0;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (grid[r][c] == 1)
maxArea = Math.max(maxArea, dfsArea(grid, r, c));
return maxArea;
}
int dfsArea(int[][] grid, int r, int c) {
int m = grid.length, n = grid[0].length;
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != 1) return 0;
grid[r][c] = 0; // mark visited
return 1
+ dfsArea(grid, r+1, c)
+ dfsArea(grid, r-1, c)
+ dfsArea(grid, r, c+1)
+ dfsArea(grid, r, c-1);
}Surrounded Regions — flip all 'O's not connected to border.
// LeetCode 130
void solve(char[][] board) {
int m = board.length, n = board[0].length;
// Step 1: DFS from border 'O's — mark them safe with '#'
for (int r = 0; r < m; r++) {
if (board[r][0] == 'O') dfsMark(board, r, 0);
if (board[r][n-1] == 'O') dfsMark(board, r, n-1);
}
for (int c = 0; c < n; c++) {
if (board[0][c] == 'O') dfsMark(board, 0, c);
if (board[m-1][c] == 'O') dfsMark(board, m-1, c);
}
// Step 2: Flip all 'O' → 'X', restore '#' → 'O'
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (board[r][c] == 'O') board[r][c] = 'X';
else if (board[r][c] == '#') board[r][c] = 'O';
}
void dfsMark(char[][] board, int r, int c) {
int m = board.length, n = board[0].length;
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') return;
board[r][c] = '#';
dfsMark(board, r+1, c); dfsMark(board, r-1, c);
dfsMark(board, r, c+1); dfsMark(board, r, c-1);
}void bfs(int[][] grid, int sr, int sc) {
int m = grid.length, n = grid[0].length;
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
visited[sr][sc] = true;
queue.offer(new int[]{sr, sc});
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size(); // process level by level
for (int i = 0; i < size; i++) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
System.out.println("Level " + level + ": (" + r + "," + c + ")");
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
visited[nr][nc] = true;
queue.offer(new int[]{nr, nc});
}
}
}
level++;
}
}BFS guarantees the minimum number of steps in an unweighted grid.
// Returns dist[][] where dist[r][c] = min steps from (sr,sc) to (r,c)
int[][] shortestPathBFS(int[][] grid, int sr, int sc) {
int m = grid.length, n = grid[0].length;
int[][] dist = new int[m][n];
for (int[] row : dist) Arrays.fill(row, -1);
Queue<int[]> queue = new LinkedList<>();
dist[sr][sc] = 0;
queue.offer(new int[]{sr, sc});
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& dist[nr][nc] == -1
&& grid[nr][nc] == 0) { // 0 = walkable
dist[nr][nc] = dist[r][c] + 1;
queue.offer(new int[]{nr, nc});
}
}
}
return dist;
}
// With path reconstruction
List<int[]> reconstructPath(int[][] dist, int[][] parent, int er, int ec, int n) {
List<int[]> path = new ArrayList<>();
for (int idx = er * n + ec; idx != -1; idx = parent[er][ec]) {
path.add(new int[]{idx / n, idx % n});
idx = parent[idx / n][idx % n];
}
Collections.reverse(path);
return path;
}Seed the queue with all sources at once — finds minimum distance from any source to every cell. Runs in O(M × N).
// Classic: 0-1 Matrix — distance to nearest 0 for every cell
// LeetCode 542
int[][] updateMatrix(int[][] mat) {
int m = mat.length, n = mat[0].length;
int[][] dist = new int[m][n];
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
// Seed: all 0-cells are sources with distance 0
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (mat[r][c] == 0) {
dist[r][c] = 0;
visited[r][c] = true;
queue.offer(new int[]{r, c});
}
}
}
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
dist[nr][nc] = dist[r][c] + 1;
visited[nr][nc] = true;
queue.offer(new int[]{nr, nc});
}
}
}
return dist;
}Why multi-source is better than running BFS from each cell separately:
- Running BFS from each
1-cell → O(M × N × (M × N)) = O(M²N²) - Multi-source BFS → O(M × N) — processes each cell exactly once
Use when moving between cells has cost 0 or 1. Uses a deque — O(M × N) vs Dijkstra's O(M × N × log(M × N)).
// Minimum cost to travel from top-left to bottom-right
// grid[r][c] = 0 means moving INTO this cell is free, 1 = costs 1
int zerOneBFSGrid(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dist = new int[m][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
dist[0][0] = 0;
Deque<int[]> deque = new ArrayDeque<>();
deque.offerFirst(new int[]{0, 0});
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!deque.isEmpty()) {
int[] cell = deque.pollFirst();
int r = cell[0], c = cell[1];
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
int cost = grid[nr][nc]; // 0 or 1
int newDist = dist[r][c] + cost;
if (newDist < dist[nr][nc]) {
dist[nr][nc] = newDist;
if (cost == 0) deque.offerFirst(new int[]{nr, nc}); // free — go to front
else deque.offerLast(new int[]{nr, nc}); // cost 1 — go to back
}
}
}
}
return dist[m-1][n-1];
}Real example — Minimum Obstacle Removal (LeetCode 2290):
- Move through empty cells (0) for free
- Remove obstacles (1) costs 1
- Find minimum removals from (0,0) to (m-1,n-1)
int minimumObstacles(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dist = new int[m][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
dist[0][0] = 0;
Deque<int[]> deque = new ArrayDeque<>();
deque.offerFirst(new int[]{0, 0, 0}); // r, c, cost
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!deque.isEmpty()) {
int[] curr = deque.pollFirst();
int r = curr[0], c = curr[1], d = curr[2];
if (d > dist[r][c]) continue; // stale
for (int[] dir : dirs) {
int nr = r + dir[0], nc = c + dir[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
int nd = d + grid[nr][nc];
if (nd < dist[nr][nc]) {
dist[nr][nc] = nd;
if (grid[nr][nc] == 0) deque.offerFirst(new int[]{nr, nc, nd});
else deque.offerLast(new int[]{nr, nc, nd});
}
}
}
}
return dist[m-1][n-1];
}Use Dijkstra when edge weights are non-negative integers (not just 0/1). Each cell's value represents the cost to enter that cell.
// Minimum cost path — cell values are entry costs
// LeetCode 1631 — Path With Minimum Effort
int minimumEffortPath(int[][] heights) {
int m = heights.length, n = heights[0].length;
int[][] dist = new int[m][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
dist[0][0] = 0;
// PQ: {effort, row, col}
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, 0, 0});
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int effort = curr[0], r = curr[1], c = curr[2];
if (r == m-1 && c == n-1) return effort;
if (effort > dist[r][c]) continue; // stale entry
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
// Effort = max absolute difference along path
int newEffort = Math.max(effort, Math.abs(heights[nr][nc] - heights[r][c]));
if (newEffort < dist[nr][nc]) {
dist[nr][nc] = newEffort;
pq.offer(new int[]{newEffort, nr, nc});
}
}
}
}
return dist[m-1][n-1];
}Generic Dijkstra on weighted grid:
// grid[r][c] = cost to enter cell (r,c)
int dijkstraGrid(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dist = new int[m][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
dist[0][0] = grid[0][0];
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{grid[0][0], 0, 0});
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int cost = curr[0], r = curr[1], c = curr[2];
if (cost > dist[r][c]) continue; // stale
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
int newCost = dist[r][c] + grid[nr][nc];
if (newCost < dist[nr][nc]) {
dist[nr][nc] = newCost;
pq.offer(new int[]{newCost, nr, nc});
}
}
}
}
return dist[m-1][n-1];
}When to use which shortest-path algorithm on a grid:
Unweighted (all moves cost 1) → BFS O(M×N)
Weights are 0 or 1 → 0-1 BFS O(M×N)
Weights are small integers (0..k) → Dial's algo O(M×N×k)
Non-negative arbitrary weights → Dijkstra O(M×N×log(M×N))
Negative weights (rare in grids) → Bellman-Ford O((M×N)²)
A* uses a heuristic to prioritize cells closer to the goal — faster than Dijkstra in practice for single-target pathfinding.
int aStarGrid(int[][] grid, int[] start, int[] goal) {
int m = grid.length, n = grid[0].length;
int[][] gCost = new int[m][n]; // cost from start
for (int[] row : gCost) Arrays.fill(row, Integer.MAX_VALUE);
gCost[start[0]][start[1]] = 0;
// PQ sorted by f = g + h (estimated total cost)
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{heuristic(start, goal), start[0], start[1]});
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int f = curr[0], r = curr[1], c = curr[2];
if (r == goal[0] && c == goal[1]) return gCost[r][c];
// Prune stale entries
if (f - heuristic(new int[]{r,c}, goal) > gCost[r][c]) continue;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 0) {
int newG = gCost[r][c] + 1;
if (newG < gCost[nr][nc]) {
gCost[nr][nc] = newG;
int h = heuristic(new int[]{nr, nc}, goal);
pq.offer(new int[]{newG + h, nr, nc});
}
}
}
}
return -1; // no path
}
// Manhattan distance — admissible for 4-directional movement
int heuristic(int[] a, int[] b) {
return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
}
// Chebyshev distance — admissible for 8-directional movement
int chebyshev(int[] a, int[] b) {
return Math.max(Math.abs(a[0] - b[0]), Math.abs(a[1] - b[1]));
}
// Euclidean distance — admissible but slower to compute
double euclidean(int[] a, int[] b) {
int dr = a[0]-b[0], dc = a[1]-b[1];
return Math.sqrt(dr*dr + dc*dc);
}A vs Dijkstra on a grid:*
| Dijkstra | A* | |
|---|---|---|
| Explores | All directions equally | Toward goal first |
| Optimality | Always optimal | Optimal if heuristic is admissible |
| Speed | O(M×N log(M×N)) | Faster in practice (fewer cells explored) |
| Use when | Multiple targets or unknown goal | Single target with spatial layout |
Fill a connected region of same-valued cells with a new value. Core building block for paint-bucket, island problems, and region labeling.
// LeetCode 733 — Flood Fill
int[][] floodFill(int[][] image, int sr, int sc, int color) {
int original = image[sr][sc];
if (original == color) return image; // already the target color — avoid infinite loop
dfsFlood(image, sr, sc, original, color);
return image;
}
void dfsFlood(int[][] image, int r, int c, int original, int newColor) {
int m = image.length, n = image[0].length;
if (r < 0 || r >= m || c < 0 || c >= n) return;
if (image[r][c] != original) return;
image[r][c] = newColor;
dfsFlood(image, r+1, c, original, newColor);
dfsFlood(image, r-1, c, original, newColor);
dfsFlood(image, r, c+1, original, newColor);
dfsFlood(image, r, c-1, original, newColor);
}
// BFS version — avoids stack overflow for large grids
int[][] floodFillBFS(int[][] image, int sr, int sc, int color) {
int original = image[sr][sc];
if (original == color) return image;
int m = image.length, n = image[0].length;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{sr, sc});
image[sr][sc] = color;
int[][] dirs = {{0,1},{0,-1},{1,0},{-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 < m && nc >= 0 && nc < n && image[nr][nc] == original) {
image[nr][nc] = color;
queue.offer(new int[]{nr, nc});
}
}
}
return image;
}Count and label all connected regions in a grid.
// Returns number of connected components (islands of 1s)
int countComponents(int[][] grid) {
int m = grid.length, n = grid[0].length;
boolean[][] visited = new boolean[m][n];
int count = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1 && !visited[r][c]) {
dfsComponent(grid, visited, r, c);
count++;
}
}
}
return count;
}
void dfsComponent(int[][] grid, boolean[][] visited, int r, int c) {
int m = grid.length, n = grid[0].length;
if (r < 0 || r >= m || c < 0 || c >= n) return;
if (visited[r][c] || grid[r][c] == 0) return;
visited[r][c] = true;
dfsComponent(grid, visited, r+1, c);
dfsComponent(grid, visited, r-1, c);
dfsComponent(grid, visited, r, c+1);
dfsComponent(grid, visited, r, c-1);
}
// Label components (assign each component a unique ID)
int[][] labelComponents(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] label = new int[m][n]; // 0 = unvisited/background
int id = 1;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (grid[r][c] == 1 && label[r][c] == 0)
bfsLabel(grid, label, r, c, id++);
return label;
}
void bfsLabel(int[][] grid, int[][] label, int sr, int sc, int id) {
int m = grid.length, n = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
label[sr][sc] = id;
queue.offer(new int[]{sr, sc});
int[][] dirs = {{0,1},{0,-1},{1,0},{-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 < m && nc >= 0 && nc < n
&& grid[nr][nc] == 1 && label[nr][nc] == 0) {
label[nr][nc] = id;
queue.offer(new int[]{nr, nc});
}
}
}
}Detect a cycle in a grid of characters/values using DFS, tracking parent direction to avoid trivially going back.
// Undirected grid cycle detection
// grid[r][c] is a character; a cycle exists if we visit a cell already visited
// through a different path
boolean hasCycle(char[][] grid) {
int m = grid.length, n = grid[0].length;
boolean[][] visited = new boolean[m][n];
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (!visited[r][c])
if (dfsCycle(grid, visited, r, c, -1, -1)) return true;
return false;
}
// pr, pc = parent cell (where we came from)
boolean dfsCycle(char[][] grid, boolean[][] visited, int r, int c, int pr, int pc) {
int m = grid.length, n = grid[0].length;
visited[r][c] = true;
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if (grid[nr][nc] != grid[r][c]) continue; // different value — not part of same region
if (nr == pr && nc == pc) continue; // came from here — skip parent
if (visited[nr][nc]) return true; // already visited via different path → cycle
if (dfsCycle(grid, visited, nr, nc, r, c)) return true;
}
return false;
}Find the longest strictly increasing path in a matrix. DFS + memoization (each cell computed once).
// LeetCode 329 — Longest Increasing Path in a Matrix
int longestIncreasingPath(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] memo = new int[m][n]; // 0 = not computed
int result = 0;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
result = Math.max(result, dfsLIP(matrix, memo, r, c));
return result;
}
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
int dfsLIP(int[][] matrix, int[][] memo, int r, int c) {
if (memo[r][c] != 0) return memo[r][c];
int m = matrix.length, n = matrix[0].length;
int best = 1;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c]) {
best = Math.max(best, 1 + dfsLIP(matrix, memo, nr, nc));
}
}
return memo[r][c] = best;
}Why no visited array? We only move to strictly larger values — no path can revisit a cell, so no cycle is possible. Memoization handles overlapping subproblems.
Count paths from top-left to bottom-right (with constraints).
// Count paths through grid where grid[r][c] == 1 is walkable
// Uses DFS + memoization
int countPaths(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] memo = new int[m][n];
for (int[] row : memo) Arrays.fill(row, -1);
return dfsCount(grid, memo, 0, 0);
}
int dfsCount(int[][] grid, int[][] memo, int r, int c) {
int m = grid.length, n = grid[0].length;
if (r == m-1 && c == n-1) return 1;
if (memo[r][c] != -1) return memo[r][c];
int count = 0;
int[][] dirs = {{0,1},{1,0}}; // only right and down for DAG paths
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < m && nc < n && grid[nr][nc] == 1)
count += dfsCount(grid, memo, nr, nc);
}
return memo[r][c] = count;
}Grid problems where you must process cells in dependency order — cells can only be processed after their prerequisites.
// Example: LeetCode 1462 or "process cells in order of increasing value"
// Kahn's-style: start with cells that have no smaller neighbors (local minima)
// Used in: Trapping Rain Water II, Swim in Rising Water
// General pattern: use a min-heap as the priority queue
// Process cells in order of their values (smallest first)
int swimInWater(int[][] grid) {
int n = grid.length;
boolean[][] visited = new boolean[n][n];
// PQ: {value, row, col} — process by smallest water level first
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{grid[0][0], 0, 0});
visited[0][0] = true;
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
int result = 0;
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int t = curr[0], r = curr[1], c = curr[2];
result = Math.max(result, t);
if (r == n-1 && c == n-1) return result;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
visited[nr][nc] = true;
pq.offer(new int[]{grid[nr][nc], nr, nc});
}
}
}
return result;
}Apply Union-Find to grid problems involving dynamic connectivity, counting islands, or grouping cells.
class GridUnionFind {
int[] parent, rank;
int components;
GridUnionFind(int[][] grid) {
int m = grid.length, n = grid[0].length;
parent = new int[m * n];
rank = new int[m * n];
components = 0;
Arrays.fill(parent, -1);
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (grid[r][c] == 1) {
parent[r * n + c] = r * n + c;
components++;
}
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
boolean union(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false;
if (rank[px] < rank[py]) parent[px] = py;
else if (rank[px] > rank[py]) parent[py] = px;
else { parent[py] = px; rank[px]++; }
components--;
return true;
}
int getComponents() { return components; }
}
// Number of Islands using Union-Find
int numIslandsUF(char[][] grid) {
int m = grid.length, n = grid[0].length;
int[] parent = new int[m * n];
int[] rankArr = new int[m * n];
Arrays.fill(parent, -1);
int count = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == '1') {
int id = r * n + c;
parent[id] = id;
count++;
}
}
}
int[][] dirs = {{0,1},{1,0}}; // only right and down to avoid double-processing
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == '1') {
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < m && nc < n && grid[nr][nc] == '1') {
int pr = findUF(parent, r * n + c);
int pnr = findUF(parent, nr * n + nc);
if (pr != pnr) {
parent[pr] = pnr;
count--;
}
}
}
}
}
}
return count;
}
int findUF(int[] parent, int x) {
if (parent[x] != x) parent[x] = findUF(parent, parent[x]);
return parent[x];
}Avoid a separate visited array by temporarily modifying the grid.
// Mark visited
char orig = grid[r][c];
grid[r][c] = '#'; // sentinel
// ... recursive calls ...
// Restore (needed for backtracking problems like Word Search)
grid[r][c] = orig;When to restore vs not:
- Don't restore (permanent mark): counting islands, flood fill, BFS traversal
- Restore (backtracking): Word Search, finding all paths, permutation-like problems
Process border cells first to handle "connected to border" problems.
// Process all 4 borders
for (int r = 0; r < m; r++) {
process(grid, r, 0); // left border
process(grid, r, n-1); // right border
}
for (int c = 0; c < n; c++) {
process(grid, 0, c); // top border
process(grid, m-1, c); // bottom border
}int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size(); // all cells at current distance
for (int i = 0; i < size; i++) {
int[] cell = queue.poll();
// process...
// add neighbors...
}
steps++;
}// Rotate 90° clockwise in-place (n×n grid)
void rotate90(int[][] matrix) {
int n = matrix.length;
// Transpose
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
// Reverse each row
for (int[] row : matrix) {
int lo = 0, hi = n - 1;
while (lo < hi) { int tmp = row[lo]; row[lo++] = row[hi]; row[hi--] = tmp; }
}
}LeetCode 994 — All rotten oranges spread simultaneously each minute. Find minimum time to rot all.
int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int fresh = 0;
// Step 1: Seed queue with all initially rotten oranges
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 2) queue.offer(new int[]{r, c});
else if (grid[r][c] == 1) fresh++;
}
}
if (fresh == 0) return 0;
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
int minutes = 0;
// Step 2: BFS level by level — each level = 1 minute
while (!queue.isEmpty() && fresh > 0) {
minutes++;
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cell = queue.poll();
for (int[] d : dirs) {
int nr = cell[0]+d[0], nc = cell[1]+d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
grid[nr][nc] = 2;
fresh--;
queue.offer(new int[]{nr, nc});
}
}
}
}
return fresh == 0 ? minutes : -1;
}LeetCode 79 — Does the word exist as a connected path in the grid?
boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (dfsWord(board, word, r, c, 0)) return true;
return false;
}
boolean dfsWord(char[][] board, String word, int r, int c, int idx) {
if (idx == word.length()) return true;
int m = board.length, n = board[0].length;
if (r < 0 || r >= m || c < 0 || c >= n) return false;
if (board[r][c] != word.charAt(idx)) return false;
char tmp = board[r][c];
board[r][c] = '#'; // mark visited
boolean found = dfsWord(board, word, r+1, c, idx+1)
|| dfsWord(board, word, r-1, c, idx+1)
|| dfsWord(board, word, r, c+1, idx+1)
|| dfsWord(board, word, r, c-1, idx+1);
board[r][c] = tmp; // restore (backtrack)
return found;
}LeetCode 286 — Fill each empty room with its distance to the nearest gate.
void wallsAndGates(int[][] rooms) {
int m = rooms.length, n = rooms[0].length;
int INF = Integer.MAX_VALUE;
Queue<int[]> queue = new LinkedList<>();
// Seed: all gates (value = 0)
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (rooms[r][c] == 0) queue.offer(new int[]{r, c});
int[][] dirs = {{0,1},{0,-1},{1,0},{-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 < m && nc >= 0 && nc < n && rooms[nr][nc] == INF) {
rooms[nr][nc] = rooms[cell[0]][cell[1]] + 1;
queue.offer(new int[]{nr, nc});
}
}
}
}LeetCode 417 — Find cells from which water can flow to BOTH oceans.
// Key insight: reverse the flow direction.
// Instead of asking "can water flow FROM this cell TO the ocean",
// ask "can water flow FROM the ocean INTO this cell?"
// DFS/BFS uphill from ocean borders.
List<List<Integer>> pacificAtlantic(int[][] heights) {
int m = heights.length, n = heights[0].length;
boolean[][] pacific = new boolean[m][n];
boolean[][] atlantic = new boolean[m][n];
// Pacific borders: top row + left col
// Atlantic borders: bottom row + right col
for (int r = 0; r < m; r++) {
bfsOcean(heights, pacific, r, 0, m, n);
bfsOcean(heights, atlantic, r, n-1, m, n);
}
for (int c = 0; c < n; c++) {
bfsOcean(heights, pacific, 0, c, m, n);
bfsOcean(heights, atlantic, m-1, c, m, n);
}
List<List<Integer>> result = new ArrayList<>();
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (pacific[r][c] && atlantic[r][c])
result.add(Arrays.asList(r, c));
return result;
}
void bfsOcean(int[][] h, boolean[][] visited, int sr, int sc, int m, int n) {
Queue<int[]> q = new LinkedList<>();
visited[sr][sc] = true;
q.offer(new int[]{sr, sc});
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!q.isEmpty()) {
int[] cell = q.poll();
int r = cell[0], c = cell[1];
for (int[] d : dirs) {
int nr = r+d[0], nc = c+d[1];
// Water flows uphill (reverse direction) — neighbor must be >= current
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& !visited[nr][nc] && h[nr][nc] >= h[r][c]) {
visited[nr][nc] = true;
q.offer(new int[]{nr, nc});
}
}
}
}LeetCode 1091 — Shortest path from (0,0) to (n-1,n-1) through 0-cells (8-directional).
int shortestPathBinaryMatrix(int[][] grid) {
int n = grid.length;
if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
if (n == 1) return 1;
Queue<int[]> queue = new LinkedList<>();
grid[0][0] = 1; // mark visited in-place with path length
queue.offer(new int[]{0, 0, 1}); // r, c, path_length
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int r = curr[0], c = curr[1], len = curr[2];
for (int[] d : dirs) {
int nr = r+d[0], nc = c+d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
if (nr == n-1 && nc == n-1) return len + 1;
grid[nr][nc] = 1; // mark visited
queue.offer(new int[]{nr, nc, len + 1});
}
}
}
return -1;
}LeetCode 1368 — Minimum cost to make all cells reachable (each cell has a default direction; changing direction costs 1).
// 0-1 BFS solution — following existing direction costs 0, changing costs 1
int minCost(int[][] grid) {
int m = grid.length, n = grid[0].length;
// Directions: 1=right,2=left,3=down,4=up
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
int[][] dist = new int[m][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
dist[0][0] = 0;
Deque<int[]> deque = new ArrayDeque<>();
deque.offerFirst(new int[]{0, 0});
while (!deque.isEmpty()) {
int[] cell = deque.pollFirst();
int r = cell[0], c = cell[1];
for (int dir = 0; dir < 4; dir++) {
int nr = r + dirs[dir][0], nc = c + dirs[dir][1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
// Cost 0 if arrow already points in this direction, else 1
int cost = (grid[r][c] == dir + 1) ? 0 : 1;
int nd = dist[r][c] + cost;
if (nd < dist[nr][nc]) {
dist[nr][nc] = nd;
if (cost == 0) deque.offerFirst(new int[]{nr, nc});
else deque.offerLast(new int[]{nr, nc});
}
}
}
}
return dist[m-1][n-1];
}LeetCode 778 — Find minimum time T such that a path exists from (0,0) to (n-1,n-1) where all cells on the path have value ≤ T.
int swimInWater(int[][] grid) {
int n = grid.length;
int[][] dist = new int[n][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
dist[0][0] = grid[0][0];
// PQ: {time, row, col}
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{grid[0][0], 0, 0});
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int t = curr[0], r = curr[1], c = curr[2];
if (r == n-1 && c == n-1) return t;
if (t > dist[r][c]) continue;
for (int[] d : dirs) {
int nr = r+d[0], nc = c+d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
// Must wait until time = max cell value on path
int newT = Math.max(t, grid[nr][nc]);
if (newT < dist[nr][nc]) {
dist[nr][nc] = newT;
pq.offer(new int[]{newT, nr, nc});
}
}
}
}
return dist[n-1][n-1];
}LeetCode 675 — Cut trees in ascending order of height; find total steps needed.
int cutOffTree(List<List<Integer>> forest) {
int m = forest.size(), n = forest.get(0).size();
// Collect all trees sorted by height
List<int[]> trees = new ArrayList<>();
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (forest.get(r).get(c) > 1)
trees.add(new int[]{forest.get(r).get(c), r, c});
trees.sort(Comparator.comparingInt(t -> t[0]));
int totalSteps = 0;
int sr = 0, sc = 0; // current position
for (int[] tree : trees) {
int tr = tree[1], tc = tree[2];
int steps = bfsSteps(forest, sr, sc, tr, tc, m, n);
if (steps == -1) return -1;
totalSteps += steps;
sr = tr; sc = tc;
}
return totalSteps;
}
int bfsSteps(List<List<Integer>> forest, int sr, int sc, int tr, int tc, int m, int n) {
if (sr == tr && sc == tc) return 0;
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
visited[sr][sc] = true;
queue.offer(new int[]{sr, sc, 0});
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
for (int[] d : dirs) {
int nr = curr[0]+d[0], nc = curr[1]+d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& !visited[nr][nc] && forest.get(nr).get(nc) != 0) {
if (nr == tr && nc == tc) return curr[2] + 1;
visited[nr][nc] = true;
queue.offer(new int[]{nr, nc, curr[2]+1});
}
}
}
return -1;
}| Algorithm | Time | Space | Best For |
|---|---|---|---|
| DFS (recursive) | O(M×N) | O(M×N) stack | Component counting, path existence, flood fill |
| DFS (iterative) | O(M×N) | O(M×N) | Same; avoids stack overflow |
| BFS | O(M×N) | O(M×N) | Shortest path (unweighted), level-order |
| Multi-Source BFS | O(M×N) | O(M×N) | Distance to nearest source |
| 0-1 BFS | O(M×N) | O(M×N) | Shortest path with 0/1 edge weights |
| Dijkstra on grid | O(M×N×log(M×N)) | O(M×N) | Shortest path with non-negative weights |
| A* on grid | O(M×N×log(M×N)) | O(M×N) | Single-target with spatial heuristic |
| Union-Find on grid | O(M×N×α) | O(M×N) | Dynamic connectivity, counting components |
| DFS + Memo | O(M×N) | O(M×N) | Longest path in DAG (no cycles), counting paths |
| Backtracking DFS | O(4^(M×N)) worst | O(M×N) | Word Search, all paths (exponential — prune hard!) |
Grid sizes and what fits in time:
| Grid Size | M×N Cells | Feasible Algorithms |
|---|---|---|
| 300×300 | 90,000 | BFS, DFS, 0-1 BFS, Dijkstra, UF |
| 1000×1000 | 1,000,000 | BFS, DFS only (no log factor) |
| 50×50 | 2,500 | All including backtracking (carefully) |
Q: When do you use DFS vs BFS on a grid?
Use BFS when you need the minimum number of steps — BFS explores level by level, guaranteeing shortest path in unweighted grids. Use DFS for connectivity problems (counting islands, flood fill, path existence), cycle detection, and when you need to explore all paths (backtracking). DFS uses O(depth) stack space; for very large grids use iterative DFS to avoid StackOverflowError.
Q: Why is multi-source BFS more efficient than running BFS from each cell?
Running BFS from each 1-cell to find the nearest 0 is O(M²N²) — each of the M×N cells launches an O(M×N) BFS. Multi-source BFS seeds the queue with all 0-cells simultaneously and expands outward once — O(M×N) total. Each cell is visited exactly once, and the BFS wave naturally assigns minimum distances.
Q: When do you choose 0-1 BFS over Dijkstra on a grid? When edge weights are strictly 0 or 1. Dijkstra with a priority queue costs O(M×N×log(M×N)) due to heap operations. 0-1 BFS with a deque is O(M×N) — no log factor because the deque acts as a two-bucket priority queue. Use 0-1 BFS for obstacle-removal problems, minimum flips, or grid-direction-change problems where moves are free or cost exactly 1.
Q: How do you handle the "in-place visited marking" trick — when to restore?
Mark the cell with a sentinel (e.g., '#') before recursing. Don't restore when you want a permanent effect (counting islands, flood fill — the cell is consumed). Always restore in backtracking problems like Word Search where multiple paths from the same starting cell are explored — without restoring, one path's traversal blocks another valid path.
Q: How do you detect when a grid problem needs Dijkstra vs BFS? Check the edge weights. If moving from any cell to any adjacent cell always costs exactly 1 (unweighted) → BFS. If moving costs 0 or 1 → 0-1 BFS. If each cell has a different positive cost to enter → Dijkstra. If you're optimizing something like "maximum of absolute differences along path" (LeetCode 1631) that isn't additive cost → Dijkstra with a modified relaxation formula. A key giveaway: if the problem says "minimum cost," "minimum effort," or "minimum time" with varying cell values → Dijkstra.
Q: Explain the reverse-flow trick used in Pacific Atlantic Water Flow. Water flows from high to low (downhill). Asking "from which cells can water reach both oceans?" directly requires checking all paths, which is expensive. The trick is to reverse the direction: start BFS/DFS from each ocean's border cells and travel uphill (to equal-or-higher neighbors). Any cell reachable from both the Pacific border BFS and the Atlantic border BFS can send water to both oceans. This converts a "can we reach the ocean from here?" question into a "can we reach this cell from the ocean?" question — two simple BFS traversals.
Q: What is the stale entry check in Dijkstra and why is it important on grids?
When we find a shorter path to a cell, we add a new entry to the priority queue — we don't update or remove the old one. The PQ may then contain multiple entries for the same cell with different distances. Without the check if (cost > dist[r][c]) continue, we'd process stale (outdated) entries and potentially explore already-optimal cells again, causing incorrect results or wasted work. The check discards any entry whose stored cost exceeds the best-known distance for that cell.
Q: How do you convert a 2D grid cell to a 1D index and why?
int id = row * numCols + col. This is needed for data structures that require a single integer key — Union-Find's parent[] array, a 1D visited[] array, or encoding a cell as a single integer in a set. Decode back with row = id / numCols, col = id % numCols. It's a standard trick that avoids 2D arrays or custom hash keys.
Q: How would you find the largest island after flipping one 0 to 1?
(LeetCode 827) Label all existing islands with Union-Find or DFS, storing each island's size. Then iterate over each 0-cell and check its unique neighboring island IDs (using a Set to deduplicate). Sum the sizes of unique neighbors + 1 (the flipped cell itself). The answer is the maximum such sum across all 0-cells. This avoids re-running BFS/DFS for each flip — O(M×N) total.
Last updated: 2026 | Language: Java 17+ | Focus: LeetCode & Interviews