Problem Statement in English

You’re given a $2$ integers m and n. They represent the number of rows and columns in a grid.

Your task is to calculate the number of paths from the origin $(0,0)$ to $(m - 1,n - 1)$.

Approach

They’ve told us that you can either move down or right at any point. So, the number of paths from a co-ordinate $(x,y)$ to $(m-1, n-1)$ (let’s call the the function that does the calculation sol) is:

$$\text{sol(x,y)} = \text{sol}(x + 1, y) + \text{sol}(x, y + 1)$$

You can actually solve this problem with just the formula. It clearly involves recursion, as can be seen from the way the function is invoked.

However, there’s one major flaw to this approach. Redundant computation.

I’m going to draw a graph, because that should make a whole lot more sense than me trying to put it into words.

    graph TD
    A((0,0)) --> B((1,0))
    A --> C((0,1))

    B --> D((2,0))
    B --> E((1,1))

    C --> F((1,1))
    C --> G((0,2))

Do you see how $(1,1)$ is called twice?

As the recursion tree generates there will be far more duplicated calls. The way we fix this, is through a technique called memoization.

All it does, is cache results, and so before we attempt to calculate the result for a co-ordinate, we check if it’s been calculated in the past. If it has, we use that stored value instead of redoing the calculation.

It’s basically a lookup table. With a fancy name.

Solution in Python


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:

        # for memoization
        lookup = {}

        def recursiveCall(x: int, y: int):
            # base case
            if x == m - 1 and y == n - 1:
                return 1
            # out of bounds
            if x >= m or y >= n:
                return 0
            # if already calculated
            if (x, y) in lookup:
                return lookup[(x, y)]

            # down and right
            down = recursiveCall(x + 1, y)
            right = recursiveCall(x, y + 1)

            # store the result
            lookup[(x + 1, y)] = down
            lookup[(x, y + 1)] = right
            lookup[(x, y)] = down + right

            # return the result
            return lookup[(x, y)]

        # begin recursion
        return recursiveCall(0, 0)

Complexity

  • Time: $O(m \times n)$
    Since we iterate over $m \times n$ co-ordinates at most.

  • Space: $O(n^2)$
    Since we might cache upto $m \times n$ values in the lookup table.

And we are done.