Unique Paths in Grid DP in DSA Java

Mental Model

Count how many ways you can move from the top-left corner to the bottom-right corner of a grid by only moving right or down.

Analogy: Imagine walking through a city grid where you can only go east or south. You want to know how many different routes you can take to reach your friend's house at the bottom-right corner.

Start (S) at top-left, End (E) at bottom-right:
S -> -> ->
↓   ↓  ↓
-> -> -> E

Dry Run Walkthrough

Input: Grid size: 3 rows x 3 columns

Goal: Find the number of unique paths from top-left to bottom-right moving only right or down

Step 1: Initialize a 3x3 grid with 1s in the first row and first column

[1, 1, 1]
[1, 0, 0]
[1, 0, 0]

Why: Only one way to reach cells in first row (all right moves) and first column (all down moves)

Step 2: Calculate paths for cell (1,1) by adding paths from top (0,1) and left (1,0)

[1, 1, 1]
[1, 2, 0]
[1, 0, 0]

Why: Paths to (1,1) = paths from above + paths from left = 1 + 1 = 2

Step 3: Calculate paths for cell (1,2) by adding paths from top (0,2) and left (1,1)

[1, 1, 1]
[1, 2, 3]
[1, 0, 0]

Why: Paths to (1,2) = 1 + 2 = 3

Step 4: Calculate paths for cell (2,1) by adding paths from top (1,1) and left (2,0)

[1, 1, 1]
[1, 2, 3]
[1, 3, 0]

Why: Paths to (2,1) = 2 + 1 = 3

Step 5: Calculate paths for cell (2,2) by adding paths from top (1,2) and left (2,1)

[1, 1, 1]
[1, 2, 3]
[1, 3, 6]

Why: Paths to (2,2) = 3 + 3 = 6

Result:

Final grid with path counts:
[1, 1, 1]
[1, 2, 3]
[1, 3, 6]
Number of unique paths = 6

Annotated Code

DSA Java

public class UniquePaths {
    public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        // Initialize first row and first column with 1
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1; // only one way to move down
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1; // only one way to move right
        }
        // Fill the dp table
        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]; // sum of top and left
            }
        }
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        int m = 3, n = 3;
        int result = uniquePaths(m, n);
        System.out.println("Number of unique paths in a " + m + "x" + n + " grid: " + result);
    }
}

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

Initialize first column with 1 because only one way to move down

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

Initialize first row with 1 because only one way to move right

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]; } }

Calculate paths for each cell by summing paths from top and left neighbors

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

Return total unique paths to bottom-right corner

Output

Number of unique paths in a 3x3 grid: 6

Complexity Analysis

Time: O(m*n) because we fill each cell in the grid once

Space: O(m*n) because we store path counts for each cell in a 2D array

vs Alternative: Compared to recursive approach without memoization which is exponential, this DP approach is efficient and avoids repeated calculations

Edge Cases

Grid with 1 row or 1 column

Only one path exists because you can only move straight right or down

DSA Java

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

Grid size 0 or negative dimensions

Function may throw error or return 0 if handled externally; current code assumes valid positive dimensions

When to Use This Pattern

When asked to count ways to move in a grid with restricted moves, use DP to build solutions from smaller subproblems by summing paths from neighbors.

Common Mistakes

Mistake: Not initializing the first row and first column with 1
Fix: Explicitly set dp[i][0] and dp[0][j] to 1 before filling the rest of the table

Mistake: Using recursion without memoization causing timeouts
Fix: Use bottom-up DP with a 2D array to store intermediate results

Summary

Calculates the number of unique paths from top-left to bottom-right in a grid moving only right or down.

Use when you need to count distinct routes in a grid with movement constraints.

The key insight is that paths to each cell equal the sum of paths to the cell above and to the left.

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