Leetcode: Unique paths
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)
:
There are 3
different ways from start to finish:
- Down, Right Right
- Right, Down, Right
- Right, Right, Down
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.
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.
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.