The Blind 75 Leetcode Series: Unique Paths

Photo by Chris Ried on Unsplash

Today, we will be working on 62. Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10^9.

We are only given m and n as the length and width of the grid. The goal is to move towards the bottom right corner from top left corner. Intuitively, we should move down and right toward the goal, but theoretically we can move in any direction. Does it still count as a unique path? This is something we need to ask. On top of this, we want to cover some corner cases as well, so…

1. What directions are we allowed to move on the grid?
2. Are we ever going to see 0 length or 0 width, basically the grid doesn’t exist? What happens if we do?

If the interviewer tells us that we can only move towards bottom and right, and we will not see a 0-length or 0-width board, then our approach becomes much simpler.

We may start with a smaller grid, and build it up as we go. For a 2 x 2, we only have 2 ways to get to the bottom-right: down -> right & right -> down.

Then we see that we only have 1 way to get to the top-right cell and bottom-left cell. In order to get to the bottom-right cell, we need to find ways to get to top-right or bottom-left cell first.

Therefore, the number of unique paths to get to a certain cell is the sum of number of unique path to get to the cell on the left & number of unique path to get to the cell on the top.

In order to track this, we can create a matrix storing the number of unique paths to get to each cell.

Using the following example to proceed……

We can create a 3 x 2 matrix. The element inside each cell for now can be 0 or, say, -1, or whatever that doesn’t confuse us with the number of unique paths when we look at the matrix. I’ll use 0.

---------
| 0 | 0 |
---------
| 0 | 0 |
---------
| 0 | 0 |
---------

Because we can only move down and to the right, we can see that the top row and the left-most column only have 1 way to get to for each cell. For the top right, we start from the top-left, and we can only move right. For the left-most column, we start from the top-left, and we can only move down.

---------
| 1 | 1 |
---------
| 1 | 0 |
---------
| 1 | 0 |
---------

Now, for the remaining of the cells, we follow the sum(left cell, top cell) approach.

---------
| 1 | 1 |
---------
| 1 | 2 |
---------
| 1 | 3 |
---------

Then simply take the bottom right cell for answer.

This is a form of dynamic programming. We build from smaller problem into bigger problem while track the results for each sub-problem.

We can put this into code

def uniquePaths(m, n):
    path = [[0] * n for _ in range(m)]
    # top row only has 1 unique path, mark all of cells with 1
    for i in range(m):
        path[i][0] = 1
    # left most column only has 1 unique path as well
    for j in range(n):
        path[0][j] = 1
    # for the rest, sum(left, top)
    for i in range(1, m):
        for j in range(1, n):
            path[i][j] = path[i-1][j] + path[i][j-1]
    return path[-1][-1]

What’s the time complexity for this approach?

We go through each cell and update the value of the cell. Then we take the last cell’s value as answer, so we have O(m*n) as time complexity where m and n are length and width of the grid.

I think this is as good as we can go for the time complexity. We do have to go through each cell at one point to know the unique paths. Can we approach this problem in another way, though?

We are building from smaller problem to bigger problem for the previous approach. Theoretically, we should be able to do the opposite: dissecting the bigger problem into smaller ones and combine the results at the end.

It sounds like a job for a recursive function as we keep breaking down the problem into smaller subset of problems until we hit the base case.

We start with the right-bottom corner, knowing that the number of unique paths to that cell is the sum of the left cell and the top cell. The number of unique paths to top cell, again, will be the sum of its left cell and top cell. We recursively do this until we hit the base case, which is the top row or left most column, where we know the number will be 1. We have the base case, and we know how to dissect the problem, now we just need to be able to track it. Tracking is simple. We either use the same grid we had earlier, or we can simply use a dictionary and use the tuple of (i, j) as key.

The technique we use here is call memoization, where we recursively break down the problem until we hit base case while passing a tracker down the subset to keep adding to it.

To put it in code:

def recursive(m, n, path):
    if (m == 1 or n == 1):
        return 1
    if (m, n) in path:
        return path[(m, n)]
    else:
        path[(m, n)] = recursive(m-1, n, path) + recursive(m, n-1, path)
        return path[(m ,n)]
def uniquePaths(m, n):
    path = {}
    return recursive(m, n, path)

For this approach, we are seeing a same time complexity, O(m * n). We have to go through each cell and calculate the unique path of the cell, so we go through total of m * n cells.

There it is! Another problem down.

Buy my a coffee: https://www.buymeacoffee.com/jonathanckz