Solution by gunpreetahuja


  • 0
    G

    Approach #1 Brute Force

    Intuition

    Use mathematical combinations formula.

    Algorithm

    In each turn, for m rows and n columns the robot can take a m-1 down moves and n-1 right moves,
    totaling n+m-2 moves. We use the combinations formula to calculate the number of unique paths possible to reach the bottom-right grid.

    Python

    class Solution(object):
        def uniquePaths(self, m, n):
            """
            :type m: int
            :type n: int
            :rtype: int
            """
            #one turn: m-1 down and n-1 right, total m+n-2 moves
    
            f_m = f_n = f_n_m = 1
            for i in range(1, m):
                f_m *= i
            print(f_m)
            for j in range(1, n):
                f_n *= j
            print(f_n)
            for k in range(1, m+n-1):
                f_n_m *= k
            print(m+n-2)
            paths = f_n_m / (f_n*f_m)
            return paths
    

    Complexity Analysis

    • Time complexity : $$O(m+n)$$.
      We need 3 for loops(to find the factorials) that run m-1, n-1, m+n-2 times, respectively, which gives m+n complexity.
    • Space complexity : $$O(1)$$.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.