Last updated on January 19th, 2025 at 02:42 am

Here, we see a Unique Paths LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Dynamic Programming

Companies

Bloomberg

Level of Question

Medium

Unique Paths LeetCode Solution

1. Problem Statement

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot 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 that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

2. Coding Pattern Used in Solution

The problem being solved in all the implementations is to calculate the number of unique paths in an m x n grid, where you can only move either down or right at any point in time. This is a classic combinatorics problem.

The coding pattern used here is Dynamic Programming (DP). The problem is solved by either:

1. Using combinatorics to calculate the number of unique paths directly (C++, Java, Python).
2. Using a 2D DP table to iteratively calculate the number of unique paths (JavaScript).

3. Code Implementation in Different Languages

3.1 Unique Paths C++

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m <=0 || n <= 0) return 0;
        long long res = 1;
        for(int i = n; i < m+n-1 ; i++){
            res = res * i / (i- n + 1);
        }
        return (int)res;       
    }
};

3.2 Unique Paths Java

class Solution {
    public int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)
            return 1;
        m--;
        n--;
        if(m < n) {
            m = m + n;
            n = m - n;
            m = m - n;
        }
        long res = 1;
        int j = 1;
        for(int i = m+1; i <= m+n; i++, j++){
            res *= i;
            res /= j;
        }  
        return (int)res;        
    }
}

3.3 Unique Paths JavaScript

var uniquePaths = function(m, n) {
    let perRow = Array(n).fill(1);
    let pathCount = Array.from( Array(m).fill( perRow ) );
    for(let y = 1 ; y < m ; y++){
        for(let x = 1 ; x < n ; x++){
            pathCount[y][x] = pathCount[y][x-1] + pathCount[y-1][x] 
        }
    }
    return pathCount[m-1][n-1]    
};

3.4 Unique Paths Python

class Solution(object):
    def uniquePaths(self, m, n):
        return math.factorial(m+n-2)/math.factorial(m-1)/math.factorial(n-1)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(1)
Java	O(n)	O(1)
JavaScript	O(m * n)	O(m * n)
Python	O(m + n)	O(1)