Unique Paths — DSA · Engineering Playbook

Unique Paths

1D DP rolling — each cell is the sum of the cell above and to its left.

Medium

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

May 16, 2026 2 min read

Problem#

A robot starts at the top-left of an m x n grid, can move only right or down, and must reach the bottom-right. Count the distinct paths.

Examples#

m=3, n=7 → 28.
m=3, n=2 → 3; m=7, n=3 → 28.

Constraints#

1 <= m, n <= 100.

Approach#

DP: paths(i, j) = paths(i-1, j) + paths(i, j-1). Roll the 2D table to one row — at each cell, dp[j] += dp[j - 1].

Solution#

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n, 1);
        for (int i = 1; i < m; ++i)
            for (int j = 1; j < n; ++j)
                dp[j] += dp[j - 1];
        return dp[n - 1];
    }
};

func uniquePaths(m int, n int) int {
    dp := make([]int, n)
    for j := range dp {
        dp[j] = 1
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[j] += dp[j-1]
        }
    }
    return dp[n-1]
}

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[n - 1]

function uniquePaths(m, n) {
    const dp = new Array(n).fill(1);
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
}

function uniquePaths(m: number, n: number): number {
    const dp: number[] = new Array(n).fill(1);
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}

Editorial#

dp[j] before the update holds paths(i-1, j); dp[j-1] is already paths(i, j-1) from this row’s earlier writes. Summing them gives paths(i, j). A closed-form C(m+n-2, m-1) is also valid but DP avoids large factorials.

Complexity#

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

Concept revision#

Climbing Stairs

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#