 # 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)``````