Leetcode: Unique paths

12 Oct 2022 by Friedrich Ewald · 4 min read · recursion

Given an m * n grid, we start in the top left corner at position (1,1). We want to move to the bottom right corner with either right or down steps. How many different combinations of right and down are there for a given grid of size m * n? We need to find an algorithm that works on arbitrarily large grids. Given this example grid of (2,3):

+---+---+---+
| S |   |   |    S = Start
+---+---+---+
|   |   | F |    F = Finish
+---+---+---+

There are 3 different ways from start to finish:

• Down, Right Right
• Right, Down, Right
• Right, Right, Down

To simplify this problem, we can think of a down move as 1 and of a right move as 0. This shows us, that we can either do 100, 010, or 001. We observe that the one is in every position. Now, two different down moves are identical, hence there are less than 2^n solutions. If we think of this problem as a backtracking problem, we can come up with a recursive algorithm. At the first position we can go either down or right. Depending on which way we go, we have to shrink the field either on the x or y-axis. We then add the result of going right to the result of going down. This step is repeated until we can only go down or right in which case we can return 1. The first solution that I submitted to Leetcode looked like this. While it is technically correct it has one flaw: A lot of fields are calculated over and over again. The algorithm goes first to the very end, then returns a 1 and goes back from there. Then for every field it has to recompute the values, even if it visited that field before. This solution produces the correct results but times out on Leetcode.

class Solution:
  def uniquePaths(self, m: int, n: int) -> int:
    if m > 1 and n > 1:
      return self.uniquePaths(m-1, n) + self.uniquePaths(m, n-1)
    return 1


if __name__ == '__main__':
  s = Solution().uniquePaths
  print(s(3,2), 3)
  print(s(3,7), 28)
  print(s(23,12), 193536720)

The final solution looks like this. I added a map to avoid calculating the same results over and over again. This is especially beneficial for larger fields where we would reach the same field via many different ways. As keys I used the coordinates of the field.

class Solution:
  def uniquePaths(self, m: int, n: int) -> int:
    memory = {}

    def inner(i, j):
      if i == 0 or j == 0:
        return 1

      if (i,j) not in memory:
        memory[(i,j)] = inner(i-1, j) + inner(i, j-1)
      return memory[(i,j)]
    
    return inner(m-1, n-1)


if __name__ == '__main__':
  s = Solution().uniquePaths
  print(s(3,2), 3)
  print(s(3,7), 28)
  print(s(23,12), 193536720)

Runtime: 44 ms, faster than 65.61% of Python3 online submissions for Unique Paths. Memory Usage: 14.3 MB, less than 6.40% of Python3 online submissions for Unique Paths.

---