#62

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Unique Paths

Calculate the number of unique paths for a robot to move on an m x n grid with only right and down movements.

Problem Statement

A robot is positioned at the top-left corner of an m x n grid and must move to the bottom-right corner. The robot can only move either right or down at each step. The task is to calculate the number of unique paths the robot can take to reach the destination.

Given the grid dimensions m and n, return the number of possible unique paths. The problem guarantees that the answer will not exceed 2 * 10^9.

Examples

Example 1

Input: m = 3, n = 7

Output: 28

Example details omitted.

Example 2

Input: m = 3, n = 2

Output: 3

From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

Right -> Down -> Down
Down -> Down -> Right
Down -> Right -> Down

Constraints

1 <= m, n <= 100

Solution Approach

Combinatorics Approach

One way to approach this problem is by using combinatorics. The robot needs to make exactly m-1 down movements and n-1 right movements, which results in a total of m+n-2 steps. The number of unique paths is equivalent to choosing (m-1) down movements from (m+n-2) total steps, or vice versa, which can be computed using the binomial coefficient formula.

Dynamic Programming Approach

A more efficient approach is using dynamic programming. You can create a 2D table where each cell represents the number of ways to reach that cell from the starting point. You initialize the first row and column as 1, since there is only one way to reach any cell in the first row (by moving right) or the first column (by moving down). Then, for each cell, you sum the values from the cell above and to the left.

Optimized Space Complexity Approach

The dynamic programming approach can be optimized in terms of space complexity. Instead of maintaining a 2D table, we can use a 1D array to store the current row's results. By iterating over the array from right to left, updating the value for the current cell based on the cell to its left, we can reduce space usage while preserving the results.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the combinatorial approach is O(m+n), which is the time required to compute the binomial coefficient. The dynamic programming solution has a time complexity of O(m n), where m and n are the grid dimensions. The space complexity of the 2D dynamic programming solution is O(m n), but this can be reduced to O(n) with the optimized approach that uses a 1D array.

What Interviewers Usually Probe

Tests whether the candidate understands combinatorics and dynamic programming.
Evaluates the ability to optimize space complexity in dynamic programming solutions.
Assesses familiarity with efficient solution strategies for grid-based problems.

Common Pitfalls or Variants

Common pitfalls

Forgetting to initialize the first row and column of the dynamic programming table.
Misunderstanding the combinatorics formula for calculating the number of paths.
Using an inefficient solution with excessive space complexity when an optimized approach is possible.

Follow-up variants

Modified problem where the robot can move in more directions (e.g., up, left, right, down).
Unique paths problem with obstacles in the grid, requiring pathfinding around blocked cells.
Grid size variation with constraints on maximum m or n values for more challenging scenarios.

FAQ

What is the most efficient way to solve the Unique Paths problem?

The most efficient way is using dynamic programming with a 1D array to optimize space complexity while preserving time efficiency. This reduces space usage to O(n).

How can combinatorics be used to solve the Unique Paths problem?

Combinatorics can be used by calculating the number of ways to arrange the required down and right movements in a sequence of total steps using the binomial coefficient formula.

What is the time complexity of the dynamic programming solution?

The time complexity of the dynamic programming solution is O(m*n), where m and n are the grid dimensions.

Can the grid dimensions be larger than 100?

No, the problem constraints ensure that the grid dimensions m and n will always be between 1 and 100.

What is the binomial coefficient formula used for in this problem?

The binomial coefficient formula is used to calculate the number of ways to choose the down or right movements from the total steps, which determines the number of unique paths.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ to represent the number of paths from the top left corner to $(i, j)$, initially $f[0][0] = 1$, and the answer is $f[m - 1][n - 1]$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        f = [[0] * n for _ in range(m)]
        f[0][0] = 1
        for i in range(m):
            for j in range(n):
                if i:
                    f[i][j] += f[i - 1][j]
                if j:
                    f[i][j] += f[i][j - 1]
        return f[-1][-1]

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        f = [[0] * n for _ in range(m)]
        f[0][0] = 1
        for i in range(m):
            for j in range(n):
                if i:
                    f[i][j] += f[i - 1][j]
                if j:
                    f[i][j] += f[i][j - 1]
        return f[-1][-1]

Solution 3

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        f = [[0] * n for _ in range(m)]
        f[0][0] = 1
        for i in range(m):
            for j in range(n):
                if i:
                    f[i][j] += f[i - 1][j]
                if j:
                    f[i][j] += f[i][j - 1]
        return f[-1][-1]

Continue Practicing

#458 poor pigs #920 number of music playlists #70 climbing stairs