Simple Combination Math, O(1) space, O(min(m, n))


  • 2

    Just calculate xCy where x is (m + n - 2), y is (min(m, n) - 1). Reason is you need to go (m + n - 2) steps total, and (m - 1) of them is down (or (n-1) of them is right).

    class Solution(object):
        def uniquePaths(self, m, n):
            """
            :type m: int
            :type n: int
            :rtype: int
            """
            cn = m + n - 2
            cr = min(m, n) - 1
            if cr == 0:
                return 1
            
            r = 1
            for i in range(cr):
                r = r * (cn - i)
            for j in range(cr):
                r = r / (j + 1)
            return r
    

Log in to reply
 

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