Unique Paths in Grid DP in DSA Java - Execution Trace

Concept Flow - Unique Paths in Grid DP

Start at top-left cell

↓

Initialize DP table with 1s in first row and column

↓

For each cell (i,j) from (1,1) to (m-1,n-1)

↓

Calculate dp[i

↓

Repeat until bottom-right cell

↓

Return dp[m-1

We fill a grid table where each cell counts paths from start by adding paths from top and left cells, starting with 1s in first row and column.

Execution Sample

DSA Java

int uniquePaths(int m, int n) {
  int[][] dp = new int[m][n];
  for (int i = 0; i < m; i++) dp[i][0] = 1;
  for (int j = 0; j < n; j++) dp[0][j] = 1;
  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];
}

This code counts unique paths from top-left to bottom-right in an m x n grid moving only down or right.

Execution Table

Step	Operation	Cell Updated	Value Computed	DP Table State
1	Initialize first column	(0,0)	1	[[1,0,0],[1,0,0],[1,0,0]]
2	Initialize first row	(0,0)	1	[[1,1,1],[1,0,0],[1,0,0]]
3	Calculate dp[1][1]	(1,1)	dp[0][1] + dp[1][0] = 1 + 1 = 2	[[1,1,1],[1,2,0],[1,0,0]]
4	Calculate dp[1][2]	(1,2)	dp[0][2] + dp[1][1] = 1 + 2 = 3	[[1,1,1],[1,2,3],[1,0,0]]
5	Calculate dp[2][1]	(2,1)	dp[1][1] + dp[2][0] = 2 + 1 = 3	[[1,1,1],[1,2,3],[1,3,0]]
6	Calculate dp[2][2]	(2,2)	dp[1][2] + dp[2][1] = 3 + 3 = 6	[[1,1,1],[1,2,3],[1,3,6]]
7	Return result	dp[2][2]	6	Final answer: 6 unique paths

💡 All cells computed, bottom-right cell dp[2][2] holds total unique paths.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
dp	[[0,0,0],[0,0,0],[0,0,0]]	[[1,0,0],[1,0,0],[1,0,0]]	[[1,1,1],[1,0,0],[1,0,0]]	[[1,1,1],[1,2,0],[1,0,0]]	[[1,1,1],[1,2,3],[1,0,0]]	[[1,1,1],[1,2,3],[1,3,0]]	[[1,1,1],[1,2,3],[1,3,6]]	[[1,1,1],[1,2,3],[1,3,6]]
m	3	3	3	3	3	3	3	3
n	3	3	3	3	3	3	3	3

Key Moments - 3 Insights

Why do we set the first row and first column cells to 1 before filling the rest?

Because from the start cell, you can only move right along the first row or down along the first column, so each cell there has exactly 1 unique path. This is shown in execution_table rows 1 and 2.

Why do we add dp[i-1][j] and dp[i][j-1] to get dp[i][j]?

Because to reach cell (i,j), you must come either from the cell above (i-1,j) or from the cell to the left (i,j-1). So total paths to (i,j) is sum of paths to those two cells, as shown in execution_table rows 3 to 6.

Why does the final answer come from dp[m-1][n-1]?

Because dp[m-1][n-1] represents the total number of unique paths to reach the bottom-right corner from the start, after filling the entire table, as shown in execution_table row 7.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the value computed for cell (1,2)?

A 3

B 4

C 2

D 1

💡 Hint

Check the 'Value Computed' column in execution_table row 4.

At which step does the dp table first contain the value 6?

A Step 5

B Step 7

C Step 6

D Step 3

💡 Hint

Look at the 'DP Table State' column and find when 6 appears.

If the grid size was 2x2 instead of 3x3, what would be the final answer in dp[m-1][n-1]?

A 1

B 2

C 3

D 4

💡 Hint

Recall that for 2x2 grid, paths = dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1.

Concept Snapshot

Unique Paths in Grid DP:
- Use a 2D dp array of size m x n
- Initialize first row and first column with 1
- For each cell dp[i][j], dp[i][j] = dp[i-1][j] + dp[i][j-1]
- Result is dp[m-1][n-1]
- Counts unique ways moving only right or down

Full Transcript

This concept shows how to count unique paths in a grid using dynamic programming. We create a 2D table dp where each cell stores the number of ways to reach it from the start. We first fill the first row and first column with 1 because there's only one way to reach those cells by moving straight right or down. Then, for each other cell, we add the number of ways to reach the cell above and the cell to the left. This builds up the total paths step by step. The final answer is in the bottom-right cell of the dp table. The execution table traces each step of filling the dp table for a 3x3 grid, showing how values accumulate. Key moments clarify why initialization is needed and why we add the two neighboring cells. The visual quiz tests understanding of these steps and the final result.

Practice

1. What does the problem "Unique Paths in Grid DP" ask you to find?
Unique Paths means:

easy

A. The maximum sum path from top-left to bottom-right in a grid

B. The shortest path length from top-left to bottom-right in a grid

C. The number of obstacles in the grid

D. The number of ways to move from top-left to bottom-right in a grid moving only right or down

Solution

1. Step 1: Understand the problem statement

   The problem asks for counting all possible paths from the top-left corner to the bottom-right corner of a grid, moving only right or down.

2. Step 2: Identify the correct interpretation

   Among the options, only counting the number of ways to move right or down matches the problem description.

3. Final Answer:

   The number of ways to move from top-left to bottom-right in a grid moving only right or down -> Option D

4. Quick Check:

   Unique Paths = Counting ways moving right/down [OK]

Hint: Unique Paths count moves right/down only [OK]

Common Mistakes:

• Confusing unique paths with shortest path
• Thinking about obstacles instead of paths
• Mixing path count with path sum

2. Which of the following Java code snippets correctly initializes a 2D DP array dp for a grid of size m x n?

easy

A. int[][] dp = new int[m][n];

B. int dp[][] = new int[n][m];

C. int dp = new int[m][n];

D. int[][] dp = new int[m];

Solution

1. Step 1: Recall Java 2D array syntax

   In Java, a 2D array is declared as int[][] dp = new int[m][n]; where m is rows and n is columns.

2. Step 2: Check each option

   int[][] dp = new int[m][n]; matches correct syntax. int dp[][] = new int[n][m]; swaps dimensions. int dp = new int[m][n]; uses wrong type. int[][] dp = new int[m]; misses second dimension.

3. Final Answer:

   int[][] dp = new int[m][n]; -> Option A

4. Quick Check:

   Java 2D array = int[][] dp = new int[m][n] [OK]

Hint: Use int[][] dp = new int[m][n] for 2D arrays [OK]

Common Mistakes:

• Swapping row and column sizes
• Missing second dimension in array creation
• Using single brackets for 2D arrays

3. What is the output of the following Java code snippet for m = 3 and n = 3?

int m = 3, n = 3;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
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];
  }
}
System.out.println(dp[m-1][n-1]);

medium

A. 3

B. 10

C. 6

D. 1

Solution

1. Step 1: Initialize first row and column

   First row and first column are set to 1, representing only one way to reach those cells.

2. Step 2: Fill dp table using sum of top and left cells

   Calculate dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2, dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3, dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3, dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6.

3. Step 3: Recalculate final cell

   dp[2][2] = 6 is incorrect for 3x3 grid unique paths. The correct number of unique paths in a 3x3 grid is 6, but let's verify carefully:
   Actually, the number of unique paths from top-left to bottom-right in a 3x3 grid moving only right or down is 6.
   Let's trace the dp table:
   Row 0: [1,1,1]
   Row 1: [1,2,3]
   Row 2: [1,3,6]
   So dp[2][2] = 6 is correct.

4. Final Answer:

   6 -> Option C

5. Quick Check:

   Unique paths in 3x3 grid = 6 [OK]

Hint: Sum ways from top and left cells to fill dp [OK]

Common Mistakes:

• Not initializing first row and column to 1
• Adding dp[i][j-1] and dp[i-1][j] incorrectly
• Off-by-one errors in loops

4. Identify the bug in the following Java code for computing unique paths in an m x n grid:

int[][] dp = new int[m][n];
for (int i = 0; i <= m; i++) dp[i][0] = 1;
for (int j = 0; j <= n; j++) dp[0][j] = 1;
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];
  }
}

medium

A. Loops use <= causing ArrayIndexOutOfBoundsException

B. dp array is not initialized

C. Sum formula is incorrect

D. No bug, code is correct

Solution

1. Step 1: Check loop boundaries for dp array

   Arrays in Java are 0-indexed, so valid indices are 0 to m-1 and 0 to n-1. Using <= m or <= n causes index out of bounds.

2. Step 2: Identify the error cause

   Loops with condition i <= m and j <= n try to access dp[m][0] or dp[0][n], which do not exist.

3. Final Answer:

   Loops use <= causing ArrayIndexOutOfBoundsException -> Option A

4. Quick Check:

   Array indices must be less than size [OK]

Hint: Use < not <= for array indices in loops [OK]

Common Mistakes:

• Using <= instead of < in loops
• Ignoring zero-based indexing
• Assuming array size includes upper bound index

5. Given a grid with obstacles represented by 1s and empty spaces by 0s, how would you modify the Unique Paths DP solution to count paths avoiding obstacles?
Choose the correct approach:

hard

A. Use recursion without memoization to handle obstacles

B. Set dp[i][j] = 0 if grid[i][j] == 1; else dp[i][j] = dp[i-1][j] + dp[i][j-1], Initialize dp[0][0] = 1 if no obstacle, Handle first row and column carefully considering obstacles

C. Set dp[i][j] = 1 if grid[i][j] == 1; else 0, Sum all dp values at the end

D. Ignore obstacles and calculate paths normally, Obstacles don't affect path count

Solution

1. Step 1: Understand obstacle effect on paths

   If a cell has an obstacle, no path can go through it, so dp value must be 0.

2. Step 2: Modify DP formula and initialization

   Set dp[i][j] = 0 if obstacle; else sum of dp from top and left. Initialize dp[0][0] = 1 only if no obstacle. First row and column must consider obstacles to stop paths beyond them.

3. Final Answer:

   Set dp[i][j] = 0 if grid[i][j] == 1; else dp[i][j] = dp[i-1][j] + dp[i][j-1], Initialize dp[0][0] = 1 if no obstacle, Handle first row and column carefully considering obstacles -> Option B

4. Quick Check:

   Obstacles block paths, dp=0 there [OK]

Hint: Set dp=0 for obstacles, sum neighbors otherwise [OK]

Common Mistakes:

• Ignoring obstacles in dp calculation
• Not initializing dp[0][0] correctly
• Not stopping path count after obstacle in first row/column