Pikachu's Journey - codepath/compsci_guides GitHub Wiki

Unit 12 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 15 mins
  • 🛠️ Topics: Dynamic Programming, Grid Traversal

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What is the goal of the problem?
    • The goal is to determine how many unique paths Pikachu can take to reach the bottom-right corner of a grid from the top-left corner.
  • What movements can Pikachu make?
    • Pikachu can move either right or down.
  • Does Pikachu need to take a fixed number of steps?
    • No, Pikachu simply needs to reach the bottom-right corner.
HAPPY CASE
Input: 
    m = 3, n = 7
Output: 
    28
Explanation:
    Pikachu can take 28 unique paths from the top-left corner to the bottom-right corner on a 3x7 grid.

EDGE CASE
Input: 
    m = 3, n = 2
Output: 
    3
Explanation:
    Pikachu can take 3 unique paths from the top-left corner to the bottom-right corner on a 3x2 grid: 
    1. Right -> Down -> Down
    2. Down -> Down -> Right
    3. Down -> Right -> Down

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Grid Traversal or Dynamic Programming, and strategies or patterns in those categories.

For Grid Traversal problems, we want to consider the following approaches:

  • Dynamic Programming (DP): This is a common approach where we maintain a DP table that tracks the number of ways to reach each cell in the grid.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use dynamic programming to calculate the number of ways to reach each cell in the grid. The number of unique ways to reach a given cell is the sum of the ways to reach the cell from above (moving down) and from the left (moving right).

Steps:

  1. Initialization:

    • Create a 2D DP table where each cell represents the number of ways to reach that cell.
    • Initialize the first row and the first column of the DP table to 1 since there is only one way to move along the edges (either all the way right or all the way down).

  2. Filling the DP Table:

    • For each remaining cell, compute the number of unique paths as the sum of the number of ways to reach the cell directly above and the cell directly to the left.

  3. Return the Result:

    • The value in the bottom-right corner of the DP table will represent the total number of unique paths from the top-left corner to the bottom-right corner.

4: I-mplement

Implement the code to solve the algorithm.

def pikachu_unique_paths(m, n):
    # Create a 2D DP table with all zeros
    dp = [[0] * n for _ in range(m)]
    
    # Initialize the first row and first column
    for i in range(m):
        dp[i][0] = 1  # Only one way to move down in the first column
    for j in range(n):
        dp[0][j] = 1  # Only one way to move right in the first row
    
    # Fill in the rest of the DP table
    for i in range(1, m):
        for j in range(1, n):
            # The number of ways to reach dp[i][j] is the sum of ways from above and from the left
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    
    # The bottom-right corner will have the total number of unique paths
    return dp[m - 1][n - 1]

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

  • Input: m = 3, n = 7
  • Expected Output: 28

Example 2:

  • Input: m = 3, n = 2
  • Expected Output: 3

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume m is the number of rows and n is the number of columns.

  • Time Complexity: O(m * n) because we need to fill the entire DP table.
  • Space Complexity: O(m * n) to store the DP table with m rows and n columns.