62. Unique Paths

← All Problems
medium Dynamic Programming
A robot is located at the top-left corner of an m x n grid. It can only move either down or right at any point in time. Given the two integers m and n, return the number of possible unique paths the robot can take to reach the bottom-right corner of the grid.

Example

m = 3, n = 3 (3x3 grid)

Output: 6

The robot must move right exactly 2 times and down exactly 2 times to go from the top-left to the bottom-right. The 6 paths correspond to the 6 different orderings of these 4 moves (e.g., RRDD, RDRD, RDDR, DRRD, DRDR, DDRR).

dp[i][j] = dp[i-1][j] + dp[i][j-1] because you can only arrive at a cell from above or from the left. The first row and first column are all 1s since there's only one way to reach them. You can optimize to a single 1D array by updating it row by row.

Why this works

You can only move right or down, so the number of ways to reach any cell equals the ways to reach the cell above it plus the ways to reach the cell to its left. The top row and left column each have exactly one path (all-right or all-down), which gives you the base cases to build from.

Step by step

  1. Initialize a 1D array — fill with 1s, representing the first row where every cell has exactly one path.
  2. Process each row — for rows 1 through m-1, update each cell by adding the value from the left neighbor.
  3. Accumulate paths — dp[j] += dp[j-1] works because dp[j] already holds paths from above (previous row), and dp[j-1] holds paths from the left (current row).
  4. Return dp[n-1] — the last cell in the array is the bottom-right corner.
Time: O(m×n) Space: O(n) 
class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1); // first row: only one way to reach each cell
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1]; // paths from above + paths from left
            }
        }
        return dp[n - 1];
    }
}

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n, 1); // first row: only one way to reach each cell
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1]; // paths from above + paths from left
            }
        }
        return dp[n - 1];
    }
};

def uniquePaths(m: int, n: int) -> int:
    dp = [1] * n  # first row: only one way to reach each cell (go right)
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]  # paths from above (old dp[j]) + paths from left (dp[j-1])
    return dp[n - 1]