Unique Paths — Solution in C++, Java, Python, Go

Given an m x n grid, a robot starts at the top-left corner and wants to reach the bottom-right corner. The robot can only move either down or right at any point. Return the number of unique paths the robot can take to reach the destination.

Examples

Example 1

Input: m = 3, n = 7
Output: 28
Explanation: There are 28 unique paths from the top-left to the bottom-right of a 3x7 grid.

Example 2

Input: m = 3, n = 2
Output: 3
Explanation: The three paths are: Right->Down->Down, Down->Down->Right, and Down->Right->Down.

Constraints

1 <= m, n <= 100

Approaches

3 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursion (Brute Force)

Intuition

From any cell (i, j), the robot can move right to (i, j+1) or down to (i+1, j). The number of paths from (i, j) to the destination is the sum of paths from the right neighbor and the downward neighbor. The base case is that any cell in the last row or last column has exactly one path (since the robot can only go in one direction).

Algorithm

If `m == 1` or `n == 1`, return `1`.
Recursively compute `uniquePaths(m - 1, n) + uniquePaths(m, n - 1)`.
Return the result.

TimeO(2^(m+n))SpaceO(m + n) for the recursion stack

Code (C++ · Java · Python · Go)

C++17

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) return 1;
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }
};

Java 21

class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) return 1;
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }
}

Python 3.12

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1:
            return 1
        return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)

Go 1.26

func uniquePaths(m int, n int) int {
    if m == 1 || n == 1 {
        return 1
    }
    return uniquePaths(m-1, n) + uniquePaths(m, n-1)
}

Approach 2

Dynamic Programming (Bottom-Up)

Intuition

Build a 2D table where dp[i][j] is the number of unique paths to reach cell (i, j). The first row and first column are all 1 because there is only one way to reach any cell along the edge. For all other cells, dp[i][j] = dp[i-1][j] + dp[i][j-1].

Algorithm

Create a 2D array `dp` of size `m x n`.
Fill the first row and first column with `1`.
For each cell `(i, j)` where `i > 0` and `j > 0`, set `dp[i][j] = dp[i-1][j] + dp[i][j-1]`.
Return `dp[m-1][n-1]`.

TimeO(m * n)SpaceO(m * n)

Code (C++ · Java · Python · Go)

C++17

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

Java 21

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

Python 3.12

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

Go 1.26

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

Approach 3

Space-Optimized DP

Intuition

Since each row only depends on the current and previous rows, we can use a single 1D array. As we process each cell left to right, dp[j] already contains the value from the row above, and dp[j-1] contains the updated value from the current row.

Algorithm

Create a 1D array `dp` of size `n`, filled with `1`.
For each row from 1 to `m - 1`:
Return `dp[n - 1]`.

TimeO(m * n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17

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];
    }
};

Java 21

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];
    }
}

Python 3.12

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

Go 1.26

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]
}

Frequently asked questions

What is the optimal time complexity of Unique Paths?

The most efficient approach in this guide ("Space-Optimized DP") runs in O(m * n) time and uses O(n) extra space. Earlier brute-force approaches are slower; see all 3 approaches above for the full progression.

What pattern does Unique Paths use?

Unique Paths is a medium-level Dynamic Programming problem involving Math, Dynamic Programming. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Unique Paths be solved without extra space?

The most space-efficient approach in this guide uses O(n) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(m + n) for the recursion stack, while the optimized version uses O(n).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...

Input

Expected Output