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)