# Find number of unique paths to reach opposite grid corner

I have m x n grid. m >= 1 ; n >= 1

I have item in the top-left corner and need to reach bottom-right corner of the grid.

Item can only move either down or right.

I need to find possible unique paths to do it.

I made two solutions for the problem: recursion (slower than the below one) and the one below.

The problem is that I run out of memory when m and n are big e.g. m == 20 and n >= 15 (more than 4 Gb is used - all free memory I have).

How can I improve my solution or there should be absolutely other way to solve the problem?


def unique_paths(m, n):
assert isinstance(m, int), "m should be integer"
assert isinstance(n, int), "n shoudl be integer"
assert m >= 1, "m should be >= 1"
assert n >= 1, "n should be >= 1"
if m == 1 and n == 1:  # border case
return 1

ch = [(m, n,)]  # for first start
s = 0  # number of unique paths
while True:
new_ch = []
while ch:
i = ch.pop()  # I assumed that if decrease len of list it would decrease memory use
if i == 1 and i == 1:  # we reached opposite corner
s += 1

# all other cases:

elif i != 1 and i != 1:
new_ch.append((i, i - 1, ))
new_ch.append((i - 1, i))

elif i == 1 and i != 1:
new_ch.append((i, i - 1,))

else:
new_ch.append((i - 1, i,))

del i  # do not need i anymore

if not new_ch:
return s
del ch
ch = new_ch
del new_ch

if __name__ == '__main__':
print(unique_paths(7, 3))  # = 28 - test case


Edit:

lru_cache is really amazing:


from functools import lru_cache

@lru_cache(128)
def numberOfPaths(m, n):
if m == 1 and n == 1:  # border case
return 1

if m != 1 and n != 1:
return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1)

if m != 1 and n == 1:
return numberOfPaths(m - 1, n)

if m == 1 and n != 1:
return numberOfPaths(m, n - 1)

if __name__ == '__main__':
print(numberOfPaths(100, 100))  # 22750883079422934966181954039568885395604168260154104734000

$$$$

• I didn't downvote, but this seems like it's less a matter of improving the code and more a matter of improving the underlying algorithm. Not sure how much a review of the code on its own will help you. :) Apr 26, 2020 at 20:19
• Close / down voter, this is not off-topic as it works with smaller bounds. Please read meta where we have explicitly allowed performance and memory improvements. We have a tag for this with ~150 questions, how's it off-topic 🤦 Apr 26, 2020 at 20:41
• @Samwise Please keep the comments for discussing how the question can be improved and the answers for how the question's code can be improved. Apr 26, 2020 at 20:42
• As they say, the right algorithm is the key. As long as you bruteforce, lru_cache is just a pair of crutches. OTOH, math does wonders. The answer to this problem is $\binom{m+n-2}{m-1}$.
– vnp
Apr 26, 2020 at 21:25
• It's a binomial coefficient
– vnp
Apr 27, 2020 at 6:43

Solution: recursion with memoization works really well! Many thanks to Samwise and vnp.

With the help of python lru_cache decorator:

@lru_cache(128)
def number_of_paths(m, n):
if m == 1 and n == 1:  # border case
result = 1

elif m != 1 and n != 1:
result = number_of_paths(m - 1, n) + number_of_paths(m, n - 1)

elif m != 1 and n == 1:
result = number_of_paths(m - 1, n)

elif m == 1 and n != 1:
result = number_of_paths(m, n - 1)

else:
raise Exception("Something went wrong!")

return result


With the help of dictionary to store results:

storage = {}
def number_of_paths_no_lru(m, n):
if storage.get((m, n,)):
return storage[(m, n)]

if m == 1 and n == 1:  # border case
result = 1

elif m != 1 and n != 1:
result = number_of_paths_no_lru(m - 1, n) + number_of_paths_no_lru(m, n - 1)

elif m != 1 and n == 1:
result = number_of_paths_no_lru(m - 1, n)

elif m == 1 and n != 1:
result = number_of_paths_no_lru(m, n - 1)

else:
raise Exception("Something went wrong!")

storage[(m, n, )] = result
return result


Tests:

if __name__ == '__main__':
print(number_of_paths(100, 100))
print(number_of_paths_no_lru(100, 100))
`