Unique Paths

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.

Approach

Use DP where dp[j] is the number of ways to reach column j in the current row. Initialize all to 1 for the first row, then for each subsequent row update dp[j] += dp[j-1].

Why It Works

To reach a cell, you can only come from the top or left. The recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1] counts all paths. The 1D array stores the previous row while updating the current row in place.

Complexity

• Time: O(m * n)
• Space: O(n)

Reference Implementation (Python)

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