62. Unique Paths

Approach 1: Combinatorics

Let us assume that the m = 3 and n = 3

The path will then always be 4 moves long: DDRR, DRDR, RDRD..... where R means Right, and D means Down.

On observation you can see that the path length will always be m-1 R's and n-1 D's to reach the bottom corner and the total path length is m+n-2

We can convert this problem into a linear one:

Given a string of length m + n - 2 fill it with m-1 R's and n-1 D's

Using combinatorics we can say that it is: m+n-2 choose m-1 i.e. (m+n-2)C(m-1) which is evaluated as the answer below

class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
di = {0:1, 1:1, 2:2}
def factorial(n):
if n in di:
return di[n]
else:
di[n] = n*factorial(n-1)
return di[n]
return int(factorial(m+n-2)/(factorial(m-1)*factorial(n-1)))

Time Complexity: O(m+n-2)

Space Complexity: O(m+n-2)

Approach 2: Use multiplication instead of factorial

Same math as above but just a different way of evaluation

Instead of using a memo-ised factorial function we can simply calculate it as below since we know the values of m and n. This solution is more memory efficient than above

class Solution:
def uniquePaths(self, m, n):
"""
https://leetcode.com/problems/unique-paths/description/
:type m: int
:type n: int
:rtype: int
"""
ma, mi = max(m-1,n-1) , min(m-1,n-1)
su = m + n - 2
k = 1
for i in range(su,ma,-1):
k = k * i
for i in range(1,mi+1):
k = k / i
return int(k)

Time Complexity: O(m+n-2)

Space Complexity: O(1)

Approach 3: Dynamic Programming

Since we can only move in 2 directions, dp[i][j] = dp[i-1][j] + dp[i][j-1]

where dp[i][j] stands for the total number of paths till location(i,j)

As for the initial conditions: dp[i][0] = 1 for all i < m and dp[0][j] for all j < n

Using this we can get the total number of paths as follows:

class Solution:
def uniquePaths(self, m, n):
"""
https://leetcode.com/problems/unique-paths/description/
:type m: int
:type n: int
:rtype: int
"""
dp = [[1]*n for _ in range(m)]
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 1
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]

‚Äč