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]