Solution by gunpreetahuja

  • 0

    Approach #1 Brute Force


    Use mathematical combinations formula.


    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.


    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
            for j in range(1, n):
                f_n *= j
            for k in range(1, m+n-1):
                f_n_m *= k
            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.