62. Unique Paths - Explanation

Description

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 & Space Complexity

You should aim for a solution as good or better than O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the grid.

Hint 1

Try to think in terms of recursion and visualize it as a decision tree, where we have two choices at each step. Can you determine the base condition and recurrence relation?

Hint 2

We recursively traverse the grid using row i and column j. At each step, we explore both possibilities: moving down or moving right, ensuring we do not go out of bounds. If we reach the bottom-right cell, we return 1.

Hint 3

This approach has exponential complexity. Can you think of a way to optimize the recursion? Maybe you should consider using a dynamic programming approach.

Hint 4

We can use memoization to cache the results of recursive calls and avoid recalculations. A hash map or a 2D array can be used to store these results.

Company Tags

1. Recursion

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:

        def dfs(i, j):
            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 & Space Complexity

Time complexity: $O(2 ^ {m + n})$
Space complexity: $O(m + n)$

Where $m$ is the number of rows and $n$ is the number of columns.

2. Dynamic Programming (Top-Down)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        memo = [[-1] * n for _ in range(m)]
        def dfs(i, j):
            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 & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns.

3. Dynamic Programming (Bottom-Up)

class Solution:
    def uniquePaths(self, 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 & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns.

4. Dynamic Programming (Space Optimized)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        row = [1] * n

        for i in range(m - 1):
            newRow = [1] * n
            for j in range(n - 2, -1, -1):
                newRow[j] = newRow[j + 1] + row[j]
            row = newRow
        return row[0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(n)$

Where $m$ is the number of rows and $n$ is the number of columns.

5. Dynamic Programming (Optimal)

class Solution:
    def uniquePaths(self, 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 & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(n)$

Where $m$ is the number of rows and $n$ is the number of columns.

6. Math

class Solution:
    def uniquePaths(self, 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 & Space Complexity

Time complexity: $O(min(m, n))$
Space complexity: $O(1)$

Where $m$ is the number of rows and $n$ is the number of columns.