Unique Paths Leetcode Solution

In this post, you will know how to solve the Unique Paths Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.

Problem

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

Constraints:

• 1 <= m, n <= 100

Unique Paths Leetcode Solutions in Python

class Solution:
  def uniquePaths(self, m: int, n: int) -> int:
    # dp[i][j] := unique paths from (0, 0) to (i, j)
    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[-1][-1]

Unique Paths Leetcode Solutions in CPP

class Solution {
 public:
  int uniquePaths(int m, int n) {
    // dp[i][j] := unique paths from (0, 0) to (i, j)
    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];
  }
};

Unique Paths Leetcode Solutions in Java

class Solution {
  public int uniquePaths(int m, int n) {
    // dp[i][j] := unique paths from (0, 0) to (i, j)
    int[][] dp = new int[m][n];
    Arrays.stream(dp).forEach(row -> Arrays.fill(row, 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];
  }
}

Note: This problem Unique Paths is generated by Leetcode but the solution is provided by  BrokenProgrammers. This tutorial is only for Educational and Learning purposes.

Next: Trapping Rain Water Leetcode Solution