Unique Paths in Grid DP in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Unique Paths Calculation in 3x3 Grid

What is the output of the following Java code that calculates unique paths in a 3x3 grid?

DSA Java

public class UniquePaths {
    public static 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];
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 3));
    }
}

A 6

B 3

C 1

D 9

💡 Hint

Think about how many ways you can move right or down to reach the bottom-right corner.

The number of unique paths in a 3x3 grid moving only right or down is 6. The dp table counts all possible ways to reach each cell by summing ways from the top and left cells.

🧠 Conceptual

intermediate

Understanding Base Cases in Unique Paths DP

Why do we initialize the first row and first column of the DP table with 1 in the Unique Paths problem?

A Because the first row and column represent obstacles that block paths.

B Because the first row and column represent the maximum number of paths possible.

C Because the first row and column are always unreachable in the grid.

D Because there is only one way to reach any cell in the first row or first column by moving only right or down.

💡 Hint

Think about how you can move from the start to cells in the first row or column.

You can only move right or down. To reach any cell in the first row, you must move right all the way. Similarly, to reach any cell in the first column, you must move down all the way. So, there is exactly one path to each of these cells.

🔧 Debug

advanced

Identify the Bug in Unique Paths DP Implementation

What error will the following Java code produce when calculating unique paths for a 3x3 grid?

DSA Java

public class UniquePaths {
    public static 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];
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 3));
    }
}

A NullPointerException

B ArrayIndexOutOfBoundsException

C Returns 0

D Returns 6

💡 Hint

Check the loop conditions for initializing the dp array.

The loops initializing the first row and column use <= which causes the index to go out of bounds since arrays are 0-indexed. This throws ArrayIndexOutOfBoundsException.

🚀 Application

advanced

Number of Unique Paths in a 4x5 Grid

What is the number of unique paths from the top-left to bottom-right corner in a 4x5 grid moving only right or down?

A 35

B 56

C 70

D 20

💡 Hint

Use the formula for combinations or the DP approach to count paths.

The number of unique paths in a 4x5 grid moving only right or down is 35. This is calculated using the combinatorial formula C(4+5-2, 4-1) = C(7,3) = 35.

❓ Predict Output

expert

Output of Unique Paths with Obstacles

What is the output of the following Java code that calculates unique paths in a 3x3 grid with an obstacle at position (1,1)?

DSA Java

public class UniquePathsWithObstacles {
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) break;
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 1) break;
            dp[0][j] = 1;
        }
        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];
    }

    public static void main(String[] args) {
        int[][] grid = {
            {0,0,0},
            {0,1,0},
            {0,0,0}
        };
        System.out.println(uniquePathsWithObstacles(grid));
    }
}

A 3

B 4

C 2

D 1

💡 Hint

Consider how the obstacle blocks some paths and how DP accumulates paths avoiding it.

The obstacle at (1,1) blocks paths through that cell. The DP counts paths avoiding it. The total unique paths from top-left to bottom-right are 2.

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