0062 - Unique Paths (Medium)
Problem Link
https://leetcode.com/problems/unique-paths/
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 * 10^9.
Example 1:
Input: m = 3, n = 7
Output: 28Example 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 -> DownConstraints:
1 <= m, n <= 100
Approach 1 : Math
We need to make steps in total. How many ways to choose from right steps and down steps out of the total steps?
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
return comb(m - 1 + n - 1, min(m - 1, n - 1))Approach 2: Dynamic programming (Top Down) Memoization
We begin with the position (0,0). At any position (i,j), we make a recursive call to (i+1,j) and (i,j+1) to get the number of paths to the right and below the current node. If (i,j) goes out of bound, there can exist no path from it so we simply return 0. If we reach (n-1,m-1), we have found a path and so in this case we return 1.
We are using memoization to store already computed value so it will reduce runtime by just accessing the already computed value
class Solution {
HashMap<String, Integer> hm = new HashMap<String, Integer>();
public int uniquePaths(int m, int n) {
String search = Integer.toString(m) + "#" + Integer.toString(n);
if (hm.containsKey(search)) {
return hm.get(search);
} else if (m == 1 && n == 1) {
return 1;
} else if (m == 0 || n == 0) {
return 0;
} else {
hm.put(search, uniquePaths(m - 1, n) + uniquePaths(m, n - 1));
return hm.get(search);
}
}
}Approach 3: Dynamic programming (Bottom Up)
# Time Complexity: O(n * m)
# Space Complexity: O(n)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
row = [1] * n
# go through all rows exept the last one
for i in range(m - 1):
new_row = [1] * n
# go through every column except the right most column
# because the last value in every row is 1
# start at second to last position and
# keep going until we get to the beginning (reverse order)
for j in range(n - 2, -1, -1):
# right value + value below
new_row[j] = new_row[j + 1] + row[j]
# update the row
row = new_row
return row[0]