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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Unique Paths Calculation in 3x3 Grid

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

DSA Rust

fn unique_paths(m: usize, n: usize) -> usize {
    let mut dp = vec![vec![1usize; n]; m];
    for i in 1..m {
        for j in 1..n {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    dp[m - 1][n - 1]
}

fn main() {
    let result = unique_paths(3, 3);
    println!("{}", result);
}

A 6

B 9

C 3

D 12

💡 Hint

Think about how many ways you can move right and 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 accumulates the sum of paths from top and left cells.

❓ Predict Output

intermediate

Unique Paths Count for 2x4 Grid

What will be printed when running this Rust code that calculates unique paths in a 2x4 grid?

DSA Rust

fn unique_paths(m: usize, n: usize) -> usize {
    let mut dp = vec![vec![1usize; n]; m];
    for i in 1..m {
        for j in 1..n {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    dp[m - 1][n - 1]
}

fn main() {
    let result = unique_paths(2, 4);
    println!("{}", result);
}

A 4

B 5

C 6

D 7

💡 Hint

Count the ways to move right and down in a 2-row, 4-column grid.

The unique paths count for a 2x4 grid is 4, calculated by summing paths from above and left cells.

🔧 Debug

advanced

Identify the Error in Unique Paths DP Initialization

What error will this Rust code produce when calculating unique paths in a grid?

DSA Rust

fn unique_paths(m: usize, n: usize) -> usize {
    let mut dp = vec![vec![0usize; n]; m];
    for i in 0..m {
        dp[i][0] = 1usize;
    }
    for j in 0..n {
        dp[0][j] = 1usize;
    }
    for i in 1..m {
        for j in 1..n {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    dp[m - 1][n - 1]
}

fn main() {
    let result = unique_paths(3, 3);
    println!("{}", result);
}

A Prints 6 without error

B Compilation error due to missing semicolon

C Index out of bounds panic at dp[m][n]

D Returns 0 as output

💡 Hint

Check the indexing of dp at the return statement.

The code tries to access dp[m][n], but valid indices are 0 to m-1 and 0 to n-1, causing a runtime panic.

🧠 Conceptual

advanced

Understanding DP Table Initialization in Unique Paths

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

A To avoid division by zero errors during calculation

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

C To mark obstacles in the grid

D To store the maximum path length instead of count

💡 Hint

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

The first row and column cells can only be reached by moving straight right or down, so they have exactly one unique path.

❓ Predict Output

expert

Output of Unique Paths with Obstacle Grid

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

DSA Rust

fn unique_paths_with_obstacle(obstacle_grid: Vec<Vec<i32>>) -> i32 {
    let m = obstacle_grid.len();
    let n = obstacle_grid[0].len();
    let mut dp = vec![vec![0; n]; m];

    for i in 0..m {
        if obstacle_grid[i][0] == 1 {
            break;
        }
        dp[i][0] = 1;
    }
    for j in 0..n {
        if obstacle_grid[0][j] == 1 {
            break;
        }
        dp[0][j] = 1;
    }

    for i in 1..m {
        for j in 1..n {
            if obstacle_grid[i][j] == 1 {
                dp[i][j] = 0;
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    dp[m - 1][n - 1]
}

fn main() {
    let grid = vec![
        vec![0, 0, 0],
        vec![0, 1, 0],
        vec![0, 0, 0],
    ];
    let result = unique_paths_with_obstacle(grid);
    println!("{}", result);
}

A 0

B 4

C 3

D 2

💡 Hint

The obstacle blocks some paths; count only valid routes.

With an obstacle at (1,1), only 2 unique paths remain to reach the bottom-right corner.

Practice

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

easy

A. The number of ways to move from the top-left to bottom-right corner of a grid using only right and down moves

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

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

D. The number of obstacles in the grid

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Identify allowed moves

   Only moves to the right or down are allowed, so paths are sequences of these moves.

3. Final Answer:

   The number of ways to move from the top-left to bottom-right corner of a grid using only right and down moves -> Option A

4. Quick Check:

   Unique Paths = Count of right/down move sequences [OK]

Hint: Count paths with only right and down moves [OK]

Common Mistakes:

• Thinking about shortest path length instead of count
• Including diagonal or left moves
• Confusing with maximum sum path

2. Which of the following Rust code snippets correctly initializes a 2D vector dp of size m x n with all values set to 1?

easy

A. let dp = vec![vec![0; m]; n];

B. let dp = vec![vec![1; m]; n];

C. let dp = vec![vec![0; n]; m];

D. let dp = vec![vec![1; n]; m];

Solution

1. Step 1: Understand vector dimensions

   We want a vector with m rows and n columns, so outer vector length is m, inner vector length is n.

2. Step 2: Check initialization values

   All values should be 1, so inner vector is vec![1; n], repeated m times.

3. Final Answer:

   let dp = vec![vec![1; n]; m]; -> Option D

4. Quick Check:

   Outer length = m, inner length = n, all 1s [OK]

Hint: Outer vector size = rows (m), inner vector size = cols (n) [OK]

Common Mistakes:

• Swapping m and n in vector sizes
• Initializing with zeros instead of ones
• Using incorrect vector syntax

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

fn unique_paths(m: usize, n: usize) -> usize {
    let mut dp = vec![vec![1; n]; m];
    for i in 1..m {
        for j in 1..n {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    dp[m-1][n-1]
}

fn main() {
    println!("{}", unique_paths(3, 3));
}

medium

A. 9

B. 6

C. 3

D. 1

Solution

1. Step 1: Initialize dp with 1s

   dp is a 3x3 grid with all 1s initially.

2. Step 2: Fill dp using formula dp[i][j] = dp[i-1][j] + dp[i][j-1]

   Calculate dp values row by row: - 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. Final Answer:

   6 -> Option B

4. Quick Check:

   Unique paths in 3x3 grid = 6 [OK]

Hint: Use dp formula and fill row-wise [OK]

Common Mistakes:

• Not initializing first row and column with 1
• Adding dp[i][j-1] and dp[i-1][j] incorrectly
• Returning wrong dp cell

4. Identify the bug in this Rust function for unique paths and select the fix:

fn unique_paths(m: usize, n: usize) -> usize {
    let mut dp = vec![vec![0; n]; m];
    for i in 0..m {
        for j in 0..n {
            if i == 0 || j == 0 {
                dp[i][j] = 1;
            } else {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    dp[m][n]
}

medium

A. Change return to dp[m-1][n-1]

B. Initialize dp with ones instead of zeros

C. Change loops to start from 1 instead of 0

D. Remove the if condition inside loops

Solution

1. Step 1: Check dp indexing at return

   dp indices go from 0 to m-1 and 0 to n-1, so dp[m][n] is out of bounds and causes error.

2. Step 2: Fix return statement

   Return dp[m-1][n-1] to get bottom-right cell value.

3. Final Answer:

   Change return to dp[m-1][n-1] -> Option A

4. Quick Check:

   Return dp[m-1][n-1] to avoid index error [OK]

Hint: Return dp[m-1][n-1], not dp[m][n] [OK]

Common Mistakes:

• Returning dp[m][n] causing runtime panic
• Not initializing first row and column
• Starting loops incorrectly

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 skip obstacles

B. Ignore obstacles and use normal unique paths formula; obstacles don't affect path count

C. Initialize dp with zeros; set dp[0][0] = 1 if no obstacle; for each cell, if obstacle, dp[i][j] = 0 else dp[i][j] = dp[i-1][j] + dp[i][j-1]

D. Initialize dp with ones everywhere; subtract paths passing through obstacles at the end

Solution

1. Step 1: Initialize dp considering obstacles

   Set dp cells to 0 if obstacle present; dp[0][0] = 1 only if start is free.

2. Step 2: Update dp values skipping obstacles

   For each cell, if obstacle, dp[i][j] = 0; else dp[i][j] = dp[i-1][j] + dp[i][j-1]. This counts only valid paths.

3. Final Answer:

   Initialize dp with zeros; set dp[0][0] = 1 if no obstacle; for each cell, if obstacle, dp[i][j] = 0 else dp[i][j] = dp[i-1][j] + dp[i][j-1] -> Option C

4. Quick Check:

   Obstacles block paths by setting dp cells to zero [OK]

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

Common Mistakes:

• Ignoring obstacles in dp calculation
• Subtracting paths after counting all
• Using recursion without memoization causing inefficiency