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

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)