Unique Paths

medium2D Dynamic Programming46 stepsJava · Python · C++

Count paths from the top-left to the bottom-right of an m×n grid moving only right or down. Each cell is reached from above or from the left, so dp[r][c] = dp[r−1][c] + dp[r][c−1]. The first row and column have exactly one path each.

▶ Watch the animated trace

Traced input: m = 3, n = 4 → 10. Original problem: neetcode.io/problems/count-paths

Complexity

BestO(m·n)

AverageO(m·n)

WorstO(m·n)

SpaceO(m·n)

One row of size n is enough if you overwrite in place.

Key idea

Every path into (r, c) comes from (r−1, c) or (r, c−1).
Border cells can only be reached in one way.
The closed form C(m+n−2, m−1) also works, but watch for overflow.

Common mistakes

Recursion without memoisation is exponential.
Mixing up m (rows) and n (columns).

Solution

Java

int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (r == 0 || c == 0) dp[r][c] = 1;
            else dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
        }
    }
    return dp[m - 1][n - 1];
}

Python

def uniquePaths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    return dp[m - 1][n - 1]

C++

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));
    for (int r = 1; r < m; r++) {
        for (int c = 1; c < n; c++) {
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
        }
    }
    return dp[m - 1][n - 1];
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single cell You're already there.	`m = 1, n = 1`	`1`
Single row Only right moves.	`m = 1, n = 5`	`1`
Square C(4, 2) = 6.	`m = 3, n = 3`	`6`