Fastest Simplest Explained Code. T=O(min(n+m)) Space= O(1) Python


#1

class Solution:
# @param A : integer
# @param B : integer
# @return an integer
def uniquePaths(self, A, B):

    # lets say we have 5,3
    # then he have 4 (5-1) rights and 2 (3-1) downs
    # target is to compute the number of ways they can be arranged
    # Down -D
    # right - R
    # DDRRRR,DRDRRR, DRRDRR, DRRRDR, DRRRRD, RDDRRR, RDRDRR .......
    # the idea would be to find how many ways 
    # can you arrange 6 items out of which 
    # 4 is of one type and 2 is of another Type
    # The solution would be 6!/(4!*2!)
    # So the solution is (A+B)! / (A! * B!)
    
    A=A-1
    B=B-1
    total =A+B
    
    smaller=min(A,B)
    larger=max(A,B)
    
    if smaller<0 :
        return 0
    if smaller==0:
        return 1
    
    # Now we optimize how we comput this value. If A is larger then (A+B)! will surely contain A!
    # So we can right it as
    # (A+B)! / (A! * B!)
    # dividing numerator and denomenator by A!
    # {(A+B) * (A+B-1) * (A+B-1) .... * (A+1) * A!} / (A! *B!)
    # {(A+B) * (A+B-1) * (A+B-1) .... * (A+1)} / (B!)
    # Now we compute B! lets say bF
    # We evaluate {(A+B) * (A+B-1) * (A+B-1) .... * (A+1)} and divide by B!
    
    smallerNumFactorial=1
    for i in range(2,smaller+1):
        smallerNumFactorial*=i  #same as bF or B!
    reducedNumerator = 1    
    for i in range (larger+1,total+1):
        reducedNumerator*=i
    #print(reducedNumerator,smallerNumFactorial)    
    return int(reducedNumerator/smallerNumFactorial)