Unique Paths medium

Problem Statement

A robot is located at the top-left corner of a 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?

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 -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Steps to Solve

  1. Base Cases: If either m or n is 1, there's only one path.

  2. Recursive Approach (Inefficient): We can recursively explore all possible paths. Each step, we can either move right or down. This leads to exponential time complexity, making it unsuitable for larger grids.

  3. Dynamic Programming: This problem exhibits overlapping subproblems (repeated calculations). Dynamic programming efficiently solves this by storing the results of subproblems. We create a 2D array dp of size m x n, where dp[i][j] stores the number of unique paths to reach cell (i, j).

  4. Initialization: dp[0][j] = 1 for all j (only one way to reach any cell in the first row by moving right), and dp[i][0] = 1 for all i (only one way to reach any cell in the first column by moving down).

  5. Iteration: We iterate through the dp array, calculating dp[i][j] = dp[i-1][j] + dp[i][j-1]. This represents the sum of paths reaching the cell from above and from the left.

Explanation

The dynamic programming approach cleverly avoids redundant calculations. Each cell's value represents the accumulated number of paths leading to it. By building up from the base cases (the edges of the grid), we efficiently calculate the total paths to the bottom-right corner.

Code (Python)

def uniquePaths(m: int, n: int) -> int:
    """
    Calculates the number of unique paths from top-left to bottom-right in an m x n grid.
    """
    dp = [[0] * n for _ in range(m)]  # Initialize DP table

    # Base cases: Fill the first row and column with 1s
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1

    # Iterate and fill 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]

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

Complexity

  • Time Complexity: O(m*n) - We iterate through the m x n DP table once.
  • Space Complexity: O(m*n) - We use a DP table of size m x n. This can be optimized to O(min(m,n)) by using only a 1D array. (A space optimized solution is possible but adds complexity to the understanding, so this version focuses on clarity)