Unique Paths
Problem Statement
There is an m x n
grid where you are allowed to move either down or to the right at any point in time.
Given the two integers m
and n
, return the number of possible unique paths that can be taken from the top-left corner of the grid (grid[0][0]
) to the bottom-right corner (grid[m - 1][n - 1]
).
You may assume the output will fit in a 32-bit integer.
Example 1:
Input: m = 3, n = 6
Output: 21
Example 2:
Input: m = 3, n = 3
Output: 6
Constraints:
1 <= m, n <= 100
Recommended Time and Space Complexity
You should aim for a solution with O(m*n)
time and O(1)
space, where m
and n
are the dimensions of the grid.
Hint 1
Consider how the number of paths to a given cell relates to the number of paths to its neighboring cells.
Hint 2
Dynamic programming can be used to build a table of paths from the top-left to each cell.
Hint 3
For the space-optimized solutions, you can maintain only one or two rows instead of the entire grid.
Solution
Recursion
def unique_paths(m: int, n: int) -> int: def dfs(i: int, j: int) -> int: if i == (m - 1) and j == (n - 1): return 1 if i >= m or j >= n: return 0 return dfs(i, j + 1) + dfs(i + 1, j)
return dfs(0, 0)
Time complexity: O(2 ^ {m + n})
Space complexity: O(m + n)
Dynamic Programming (Top-Down)
def unique_paths(m: int, n: int) -> int: memo = [[-1] * n for _ in range(m)]
def dfs(i: int, j: int) -> int: if i == (m - 1) and j == (n - 1): return 1 if i >= m or j >= n: return 0 if memo[i][j] != -1: return memo[i][j]
memo[i][j] = dfs(i, j + 1) + dfs(i + 1, j) return memo[i][j]
return dfs(0, 0)
Time complexity: O(m * n)
Space complexity: O(m * n)
Dynamic Programming (Bottom-Up)
def unique_paths(m: int, n: int) -> int: dp = [[0] * (n + 1) for _ in range(m + 1)] dp[m - 1][n - 1] = 1
for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): dp[i][j] += dp[i + 1][j] + dp[i][j + 1]
return dp[0][0]
Time complexity: O(m * n)
Space complexity: O(m * n)
Dynamic Programming (Space Optimized)
def unique_paths(m: int, n: int) -> int: row = [1] * n
for i in range(m - 1): new_row = [1] * n for j in range(n - 2, -1, -1): new_row[j] = new_row[j + 1] + row[j] row = new_row return row[0]
Time complexity: O(m * n)
Space complexity: O(n)
Dynamic Programming (Optimal)
def unique_paths(m: int, n: int) -> int: dp = [1] * n for i in range(m - 2, -1, -1): for j in range(n - 2, -1, -1): dp[j] += dp[j + 1]
return dp[0]
Time complexity: O(m * n)
Space complexity: O(n)
Math
def unique_paths(m: int, n: int) -> int: if m == 1 or n == 1: return 1 if m < n: m, n = n, m
res = j = 1 for i in range(m, m + n - 1): res *= i res //= j j += 1
return res
Time complexity: O(min(m, n))
Space complexity: O(1)