Pattern 2: Grid Traversal Problems

The 2D Foundation Pattern: Move through 2D grid, build each cell from cells you've already visited (typically top/left).

---

The Core Pattern

THE MENTAL MODEL

Imagine you're walking through a city grid where:

1. You can only move right or down (or sometimes diagonal)
2. Each intersection has a value or cost
3. You build your answer at each intersection from the intersections you've already visited
4. You can't visit an intersection until you've computed its dependencies

This is Grid Traversal DP.

Pattern Recognition

WHEN YOU SEE THIS PATTERN

Keywords: "grid", "matrix", "paths", "reach (i,j)", "m×n board", "2D array"

Structure:

• 2D grid/matrix to traverse
• Each cell depends on neighboring cells
• Building solution cell-by-cell

State: dp[i][j] represents "best answer reaching/at cell (i,j)"

Transition: Build from already-computed neighbors:

• dp[i-1][j] (from top)
• dp[i][j-1] (from left)
• dp[i-1][j-1] (from diagonal)

---

Category 1: Core Pattern Problems

1. Unique Paths (LC 62)

PROBLEM

A robot is located at the top-left corner of an m × n grid. The robot can only move down or right. How many possible unique paths are there to reach the bottom-right corner?

State Definition: dp[i][j] = number of ways to reach cell (i, j)

Transition: dp[i][j] = dp[i-1][j] + dp[i][j-1]

• Paths from above: dp[i-1][j]
• Paths from left: dp[i][j-1]

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];

    // Base case: first row and column (only one way)
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;

    // Fill the grid
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

    return dp[m-1][n-1];
}

THE FOUNDATION INSIGHT

At any cell, the number of ways to reach it = ways to reach from top + ways to reach from left.

This is the counting version of grid DP.

📚 Deep Dive: The Discovery Journey →

Learn how the human brain naturally discovers this solution, from first principles to optimized implementation.

---

2. Unique Paths II (LC 63) - With Obstacles

State Definition: dp[i][j] = number of ways to reach (i,j) (0 if obstacle)

Transition:

if (grid[i][j] == 1) {  // obstacle
    dp[i][j] = 0;
} else {
    dp[i][j] = dp[i-1][j] + dp[i][j-1];
}

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;

    if (obstacleGrid[0][0] == 1) return 0;

    int[][] dp = new int[m][n];
    dp[0][0] = 1;

    // First column
    for (int i = 1; i < m; i++) {
        dp[i][0] = (obstacleGrid[i][0] == 0 && dp[i-1][0] == 1) ? 1 : 0;
    }

    // First row
    for (int j = 1; j < n; j++) {
        dp[0][j] = (obstacleGrid[0][j] == 0 && dp[0][j-1] == 1) ? 1 : 0;
    }

    // Fill the grid
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }

    return dp[m-1][n-1];
}

📚 Deep Dive: When Reality Gets Messy →

Learn how to adapt your solution when obstacles are added, and why the core logic still works.

---

3. Minimum Path Sum (LC 64)

PROBLEM

Given an m × n grid filled with non-negative numbers, find a path from top-left to bottom-right which minimizes the sum of all numbers along the path. You can only move right or down.

State Definition: dp[i][j] = minimum sum to reach cell (i,j)

Transition: dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int[][] dp = new int[m][n];

    dp[0][0] = grid[0][0];

    // First column
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }

    // First row
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }

    // Fill the grid
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }

    return dp[m-1][n-1];
}

COUNTING vs OPTIMIZATION

• Unique Paths: Add paths (counting)
• Minimum Path Sum: Take min + cost (optimization)

Same structure, different operation!

---

4. Dungeon Game (LC 174)

State Definition: dp[i][j] = minimum health needed at (i,j) to reach the end

Transition: dp[i][j] = Math.max(1, Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])

REVERSE TRAVERSAL!

This problem requires backward DP (from bottom-right to top-left) because you need to know the future health requirement.

public int calculateMinimumHP(int[][] dungeon) {
    int m = dungeon.length;
    int n = dungeon[0].length;
    int[][] dp = new int[m][n];

    // Start from bottom-right
    dp[m-1][n-1] = Math.max(1, 1 - dungeon[m-1][n-1]);

    // Last column (can only go down)
    for (int i = m - 2; i >= 0; i--) {
        dp[i][n-1] = Math.max(1, dp[i+1][n-1] - dungeon[i][n-1]);
    }

    // Last row (can only go right)
    for (int j = n - 2; j >= 0; j--) {
        dp[m-1][j] = Math.max(1, dp[m-1][j+1] - dungeon[m-1][j]);
    }

    // Fill from bottom-right to top-left
    for (int i = m - 2; i >= 0; i--) {
        for (int j = n - 2; j >= 0; j--) {
            int minHealthNeeded = Math.min(dp[i+1][j], dp[i][j+1]);
            dp[i][j] = Math.max(1, minHealthNeeded - dungeon[i][j]);
        }
    }

    return dp[0][0];
}

---

5. Triangle (LC 120)

State Definition: dp[i][j] = minimum sum from top to position (i,j) in triangle

Transition: dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]

public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();
    int[][] dp = new int[n][n];

    dp[0][0] = triangle.get(0).get(0);

    for (int i = 1; i < n; i++) {
        // First element (can only come from dp[i-1][0])
        dp[i][0] = dp[i-1][0] + triangle.get(i).get(0);

        // Middle elements
        for (int j = 1; j < i; j++) {
            dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle.get(i).get(j);
        }

        // Last element (can only come from dp[i-1][i-1])
        dp[i][i] = dp[i-1][i-1] + triangle.get(i).get(i);
    }

    // Find minimum in last row
    int minPath = dp[n-1][0];
    for (int j = 1; j < n; j++) {
        minPath = Math.min(minPath, dp[n-1][j]);
    }

    return minPath;
}

IRREGULAR GRID

Triangle is a non-rectangular grid. Each row i has i+1 elements. Same DP pattern, different boundaries!

---

Category 2: Counting Ways

6. Unique Paths III (LC 980)

State Definition: dp[i][j][visited] = number of ways to reach (i,j) having visited visited cells

Transition: From neighbors with proper visited count (DFS with memoization)

Pattern Extension: Add a 3rd dimension to track which cells have been visited.

---

7. Out of Boundary Paths (LC 576)

State Definition: dp[i][j][moves] = number of paths from (i,j) that go out of bounds using at most moves moves

Transition: dp[i][j][k] = sum(dp[neighbors][k-1])

---

8. Knight Probability in Chessboard (LC 688)

State Definition: dp[i][j][k] = probability that knight is at (i,j) after k moves

Transition: dp[i][j][k] = sum(dp[neighbors][k-1]) / 8

public double knightProbability(int n, int k, int row, int column) {
    double[][][] dp = new double[k + 1][n][n];
    int[][] dirs = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};

    dp[0][row][column] = 1.0;

    for (int move = 1; move <= k; move++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int[] dir : dirs) {
                    int pi = i - dir[0];
                    int pj = j - dir[1];
                    if (pi >= 0 && pi < n && pj >= 0 && pj < n) {
                        dp[move][i][j] += dp[move-1][pi][pj] / 8.0;
                    }
                }
            }
        }
    }

    double probability = 0.0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            probability += dp[k][i][j];
        }
    }

    return probability;
}

---

9. Number of Ways to Arrive at Destination (LC 1976)

State Definition: Grid-like state: dp[node] = number of ways to reach node via shortest paths

Transition: From shortest path predecessors

Pattern Recognition: Graph DP that feels like grid DP.

---

10. Cherry Pickup (LC 741)

State Definition: dp[r1][c1][r2] = maximum cherries collected by two paths

• Person 1 at (r1, c1)
• Person 2 at (r2, c2) where c2 = r1 + c1 - r2

Transition: Try all 4 combinations of previous cells (down/right for each person)

ADVANCED PROBLEM

This is one of the hardest grid DP problems. It requires tracking two simultaneous paths through the grid.

---

Category 3: Cost Optimization

11. Maximal Square (LC 221)

State Definition: dp[i][j] = side length of largest square with bottom-right corner at (i,j)

Transition: dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

public int maximalSquare(char[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    int[][] dp = new int[m][n];
    int maxSide = 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '1') {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = Math.min(
                        Math.min(dp[i-1][j], dp[i][j-1]),
                        dp[i-1][j-1]
                    ) + 1;
                }
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }

    return maxSide * maxSide;
}

WHY MIN OF THREE NEIGHBORS?

For a square to extend at (i,j):

• There must be a square above: dp[i-1][j]
• There must be a square to the left: dp[i][j-1]
• There must be a square diagonally: dp[i-1][j-1]

The smallest of these limits how big the square can be.

---

12. Minimum Falling Path Sum (LC 931)

State Definition: dp[i][j] = minimum sum to reach (i,j)

Transition: dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + matrix[i][j]

public int minFallingPathSum(int[][] matrix) {
    int n = matrix.length;
    int[][] dp = new int[n][n];

    // First row
    for (int j = 0; j < n; j++) {
        dp[0][j] = matrix[0][j];
    }

    // Fill remaining rows
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int minPrev = dp[i-1][j];
            if (j > 0) minPrev = Math.min(minPrev, dp[i-1][j-1]);
            if (j < n-1) minPrev = Math.min(minPrev, dp[i-1][j+1]);

            dp[i][j] = minPrev + matrix[i][j];
        }
    }

    // Find minimum in last row
    int minPath = dp[n-1][0];
    for (int j = 1; j < n; j++) {
        minPath = Math.min(minPath, dp[n-1][j]);
    }

    return minPath;
}

---

13. Minimum Falling Path Sum II (LC 1289) - No Adjacent

State Definition: dp[i][j] = minimum sum to reach (i,j)

Transition: dp[i][j] = Math.min(dp[i-1][k]) + grid[i][j] for all k ≠ j

CONSTRAINT DIFFERENCE

Unlike regular falling path, you cannot use the cell directly above. Must come from a different column.

---

14. Cherry Pickup II (LC 1463)

State Definition: dp[row][col1][col2] = maximum cherries with robot 1 at col1 and robot 2 at col2

Transition: Try all 9 combinations (3 moves × 3 moves) of previous positions

public int cherryPickup(int[][] grid) {
    int rows = grid.length;
    int cols = grid[0].length;
    int[][][] dp = new int[rows][cols][cols];

    // Initialize with negative infinity
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            Arrays.fill(dp[i][j], Integer.MIN_VALUE);
        }
    }

    dp[0][0][cols-1] = grid[0][0] + grid[0][cols-1];

    for (int row = 1; row < rows; row++) {
        for (int col1 = 0; col1 < cols; col1++) {
            for (int col2 = 0; col2 < cols; col2++) {
                // Try all 9 combinations of previous positions
                for (int dc1 = -1; dc1 <= 1; dc1++) {
                    for (int dc2 = -1; dc2 <= 1; dc2++) {
                        int prevCol1 = col1 + dc1;
                        int prevCol2 = col2 + dc2;

                        if (prevCol1 >= 0 && prevCol1 < cols &&
                            prevCol2 >= 0 && prevCol2 < cols) {

                            int cherries = grid[row][col1];
                            if (col1 != col2) cherries += grid[row][col2];

                            dp[row][col1][col2] = Math.max(
                                dp[row][col1][col2],
                                dp[row-1][prevCol1][prevCol2] + cherries
                            );
                        }
                    }
                }
            }
        }
    }

    int maxCherries = 0;
    for (int col1 = 0; col1 < cols; col1++) {
        for (int col2 = 0; col2 < cols; col2++) {
            maxCherries = Math.max(maxCherries, dp[rows-1][col1][col2]);
        }
    }

    return maxCherries;
}

---

15. Paint House II (LC 265)

State Definition: dp[i][j] = minimum cost to paint house i with color j

Transition: dp[i][j] = Math.min(dp[i-1][k]) for all k ≠ j + cost[i][j]

Grid-like Structure: Though it's about houses, the state space is 2D: [house][color]

---

Category 4: Path Properties

16. Longest Increasing Path in Matrix (LC 329)

State Definition: dp[i][j] = length of longest increasing path starting from (i,j)

Transition: dp[i][j] = Math.max(dp[neighbors]) + 1 where neighbor > current

public int longestIncreasingPath(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    int[][] dp = new int[m][n];
    int maxLen = 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            maxLen = Math.max(maxLen, dfs(matrix, i, j, dp));
        }
    }

    return maxLen;
}

private int dfs(int[][] matrix, int i, int j, int[][] dp) {
    if (dp[i][j] != 0) return dp[i][j];

    int m = matrix.length;
    int n = matrix[0].length;
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};

    int maxPath = 1;
    for (int[] dir : dirs) {
        int ni = i + dir[0];
        int nj = j + dir[1];

        if (ni >= 0 && ni < m && nj >= 0 && nj < n &&
            matrix[ni][nj] > matrix[i][j]) {
            maxPath = Math.max(maxPath, 1 + dfs(matrix, ni, nj, dp));
        }
    }

    dp[i][j] = maxPath;
    return maxPath;
}

DFS + MEMOIZATION

This problem uses DFS with memoization (top-down DP) instead of bottom-up iteration. The increasing constraint provides the topological ordering.

---

17. Maximum Non-Negative Product Path (LC 1594)

State Definition:

• maxDP[i][j] = maximum product to reach (i,j)
• minDP[i][j] = minimum product to reach (i,j)

Transition: Track both max and min (negative × negative = positive!)

---

18. Count Square Submatrices with All Ones (LC 1277)

State Definition: dp[i][j] = count of squares with bottom-right corner at (i,j)

Transition: dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

Pattern Recognition: Same as Maximal Square! The DP value represents both the square size AND the count contribution.

---

19. Paths in Matrix Whose Sum is Divisible by K (LC 2435)

State Definition: dp[i][j][remainder] = count of paths to (i,j) with sum mod k = remainder

Transition: dp[i][j][r] = dp[i-1][j][prevR] + dp[i][j-1][prevR]

---

20. Minimum Path Cost in a Grid (LC 2304)

State Definition: dp[i][j] = minimum cost to reach (i,j)

Transition: dp[i][j] = Math.min(dp[i-1][k] + moveCost[grid[i-1][k]][j]) + grid[i][j]

Extra Dimension: Movement cost depends on previous column, requiring consideration of all previous positions.

---

Bonus: Grid-Adjacent Patterns

These problems use 2D DP but operate on strings instead of grids:

Edit Distance (LC 72)

State: dp[i][j] = min edits to convert s1[0...i-1] to s2[0...j-1]

Transition: Consider insert, delete, replace operations

Longest Common Subsequence (LC 1143)

State: dp[i][j] = LCS length of s1[0...i-1] and s2[0...j-1]

Transition: Match characters or skip one

Interleaving String (LC 97)

State: dp[i][j] = can s3[0...i+j-1] be formed from s1[0...i-1] and s2[0...j-1]

Transition: Match with s1 or s2

CONCEPTUAL CONNECTION

These string problems follow the exact same pattern as grid traversal:

• 2D state space dp[i][j]
• Build from previous states
• Topological ordering (row-by-row, left-to-right)

The only difference: Instead of a physical grid, you're navigating a conceptual grid of string indices.

---

The Common Thread

WHAT MAKES THESE ALL THE SAME PATTERN?

Every problem has:

1. Two indices (i, j) representing 2D position
2. State dp[i][j] = "best answer reaching/at cell (i,j)"
3. Transition from neighbors: typically dp[i-1][j], dp[i][j-1], dp[i-1][j-1]
4. Dependency constraint: Can't compute a cell until its dependencies are computed
5. Topological order: Usually iterate row-by-row, left-to-right

Key Insight: You're building a 2D table where each cell depends on cells you've already filled. The dependency graph forms a DAG (Directed Acyclic Graph) that you traverse in topological order.

---

Pattern Recognition Checklist

USE THIS CHECKLIST

When you see a new problem, ask:

• Is there a 2D grid/matrix or two sequences?
• Do I need to compute something for each cell (i,j)?
• Does cell (i,j) depend on neighboring cells?
• Can I define dp[i][j] as "best answer at/reaching (i,j)"?
• Can I fill the grid in a consistent order (row-by-row)?

If all YES → Pattern 2: Grid Traversal

---

Common Mistakes

COMMON PITFALLS

Mistake 1: Forgetting boundary conditions

// WRONG - may access out of bounds
dp[i][j] = dp[i-1][j] + dp[i][j-1];

// RIGHT - handle first row/column separately
if (i == 0) dp[i][j] = dp[i][j-1];
else if (j == 0) dp[i][j] = dp[i-1][j];
else dp[i][j] = dp[i-1][j] + dp[i][j-1];

Mistake 2: Wrong traversal order

For forward DP (top-left to bottom-right):

// RIGHT
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        // compute dp[i][j] from dp[i-1][j] and dp[i][j-1]
    }
}

For backward DP (bottom-right to top-left):

// RIGHT
for (int i = m-1; i >= 0; i--) {
    for (int j = n-1; j >= 0; j--) {
        // compute dp[i][j] from dp[i+1][j] and dp[i][j+1]
    }
}

Mistake 3: Base case initialization

// Often need to initialize first row and column separately
for (int i = 0; i < m; i++) dp[i][0] = /* base value */;
for (int j = 0; j < n; j++) dp[0][j] = /* base value */;

---

Space Optimization

REDUCING FROM O(m×n) TO O(n)

Since each row only depends on the previous row, you can use rolling array:

Before (O(m×n)):

int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
}

After (O(n)):

int[] prev = new int[n];
int[] curr = new int[n];

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        curr[j] = prev[j] + (j > 0 ? curr[j-1] : 0);
    }
    // Swap arrays
    int[] temp = prev;
    prev = curr;
    curr = temp;
}

Or even in-place if you're careful about update order!

---

Learning Path

RECOMMENDED ORDER

Week 1: Core Foundation (Problems 1-5)

• Master basic grid DP (Unique Paths, Min Path Sum)
• Learn forward vs backward traversal
• Understand irregular grids (Triangle)

Week 2: Counting Ways (Problems 6-10)

• Add 3rd dimension for tracking state
• Practice probability calculations
• Tackle multi-path problems

Week 3: Cost Optimization (Problems 11-15)

• Learn "min of neighbors" patterns
• Practice constraint handling
• Master multi-robot coordination

Week 4: Advanced Properties (Problems 16-20)

• DFS + memoization approach
• Handle increasing/decreasing constraints
• Multi-dimensional state tracking

Total: 20 problems × 4 weeks = Pattern 2 mastery

---

Quick Reference Table

Problem	State	Neighbors	Operation	Pattern Type
Unique Paths	ways to reach (i,j)	top, left	add	Counting
Min Path Sum	min sum to (i,j)	top, left	min + cost	Optimization
Dungeon Game	min health at (i,j)	bottom, right	max(1, min - cost)	Backward
Maximal Square	square size at (i,j)	top, left, diagonal	min + 1	Constraint
Falling Path	min sum to (i,j)	3 top neighbors	min + cost	3 directions
Cherry Pickup II	max cherries	9 prev positions	max + cherries	Multi-robot
LIP in Matrix	longest path from (i,j)	4 neighbors	max + 1	DFS + memo
Edit Distance	min edits	3 prev states	min of 3 ops	String DP

---

Traversal Order Summary

DIRECTION MATTERS

Forward (top-left → bottom-right):

• Unique Paths, Min Path Sum, Triangle
• Use when future depends on past

Backward (bottom-right → top-left):

• Dungeon Game
• Use when past depends on future requirements

All cells (any order with memoization):

• Longest Increasing Path
• Use when constraints provide implicit ordering

---

Next Steps

AFTER MASTERING PATTERN 2

You're ready for:

• Pattern 3: Bounded Knapsack (resource constraints)
• Pattern 4: Interval DP (range-based problems)
• String DP variants (Edit Distance, LCS in depth)

Connection to Pattern 1:

• Pattern 1 = 1D progression
• Pattern 2 = 2D progression
• Same principles, one more dimension!

---

Final Thoughts

GRID DP IS EVERYWHERE

Grid Traversal is the most visual DP pattern. You can literally draw the dependency graph.

Master these 20 problems, and you'll:

• Recognize "this is a grid DP" instantly
• Know whether to go forward or backward
• Handle obstacles and constraints naturally
• See the connection to string DP problems

This is your 2D foundation. Build it strong.