algoadvance

A robot is located at the top-left corner of an m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there?

The grid size is m x n and is represented as:

S . . .
. . . .
. . . F

Example 1:

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

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Clarifying Questions

  1. Q: Can the robot move diagonally or only right and down? A: The robot can only move either right or down.

  2. Q: Are the grid dimensions (m and n) always positive integers? A: Yes, m and n are always positive integers greater than 0.

  3. Q: Is the result expected to be an integer representing the count of unique paths? A: Yes.

Strategy

We can use dynamic programming to solve this problem efficiently.

  1. Define the DP Table: Create a 2D list dp where dp[i][j] represents the number of unique paths to reach the cell (i, j) from (0, 0).

  2. Initialization:
    • The robot can only move right in the first row or down in the first column. Thus, each cell in the first row and first column has only one unique path leading to it from (0, 0).
  3. DP Transition:
    • For each cell (i, j), the unique paths to that cell are the sum of the paths from the cell directly above it (i-1, j) and the cell directly to the left of it (i, j-1).
    • Formulate this as dp[i][j] = dp[i-1][j] + dp[i][j-1].
  4. Final Answer: The bottom-right corner (m-1, n-1) will contain the number of unique paths from the top-left corner to the bottom-right corner.

Code

def uniquePaths(m, n):
    # Create a 2D DP table with m rows and n columns initialized to 0
    dp = [[0] * n for _ in range(m)]
    
    # Initialize the first row and first column to 1
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1
    
    # Fill in the rest of the dp table
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    # The number of unique paths to bottom-right corner is dp[m-1][n-1]
    return dp[m-1][n-1]

# Example usage:
# print(uniquePaths(3, 7)) # Output: 28
# print(uniquePaths(3, 2)) # Output: 3

Time Complexity

The time complexity of this dynamic programming solution is O(m * n) because it involves filling up each cell in the m x n grid once.

Space Complexity

The space complexity is also O(m * n) due to the storage requirements of the dp table. However, this can be optimized to O(min(m, n)) by using a single-dimensional array since we only need the current and the previous row/column at any point.

Try our interview co-pilot at AlgoAdvance.com