[Solution]Problem 80: Unique Paths[Google]

Grid traversal, Dynamic Programming ,Recursion

Hey, it’s your favorite cult leader here 🐱‍👤

On Thursdays, I will send you a problem + its solution. These solutions will help you reinforce your fundamental concepts, improve your problem-solving, and kill those Leetcode-Style Interviews. 🔥🔥💹💹

To get access to all my articles and support my crippling chocolate milk addiction, consider subscribing if you haven’t already!

p.s. you can learn more about the paid plan here.

---

I got nothing clever to say, so let’s get right into it.

This question can be found as Leetcode 62. Unique Paths.

Problem

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 * 109.

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

• 1 <= m, n <= 100

You can test your solution here

Step 1: Understanding the setup of the problem

As always, we start by reading the problem and annotating whatever stands out about the setup. On going over the problem given to us, here are some interesting observations-

1. The problem can be represented as a grid or a graph. In this case, they are equivalent. However, we will proceed to look at it as a 2D array, just for simplicities sake. Its possible representation as a graph plays a bigger role in more complex variants of the problem.

2. We can only go right or down. In other words, to get to cell a, we have to come from either the cell above a or to the left of it. To get to (r,c) we need to come from either (r-1,c) or (r,c-1)- assuming both are valid.

3. It doesn’t matter how we got to a particular location. The number of paths from that point to the destination is fixed.

4. Combining 2 and 3, we know the following-

   numPaths(r,c) = numPaths(r-1,c) + numPaths(r,c-1)

This gives us a recursive problem with the optimal substructure property that we discussed in our post on spotting greedy algorithms. As a refresher, your problem has this property if -

Your problem can be broken into sub-problems and their individual optimal solution are part of the optimal solution of the whole problem

If we wanted just one path, then we could have used a greedy algorithm. In our case, we know that our problem needs us to find all possible paths (or at least their number). This is a huge hint- nudging us toward DP.

Let’s proceed in setting up the dynamic programming approach now.

Step 2: Setting up DP

Now is when we start putting some meat on the bones of our solution. Question 1- top-down or bottom-up? We can do both here, and they are about the same effort. I’ll go bottom-up since some interviewers prefer that (although I suggest you code up the top-down for practice).

So how do we proceed from here? Time to pull out our trusty recursive function template, which I broke down in this post. Our template has the following steps-

1. Check for termination cases-

2. Do the processing

3. Move on to the recursive case-

4. Reset side effects- No backtracking for us, so this will not be needed.

Let’s attack each of these.

Step 3: Filling out the template

The first thing we want in our bottom-up cases is the base case. This might seem tricky since we are dealing with 2D array. So instead of one base-case, we actually need to have a bunch of base cases. What will these base cases be?

A good way to pick a base case is to select the cases (in our situation-locations) that we know the answer to. Which locations meet this criterion in this question?

Think about it.

No scrolling ahead without thinking

Think about the cells down the first row and first column in our grid. We can only get to them in one way- going right and down respectively. Thus, we can prepopulate all of these, and let each of these serve as a base case.

The following code will take care of this-

        for r in range(m):
            numPaths[r][0] = 1

        for c in range(n):
            numPaths[0][c] = 1

What would the processing be? In our case, the processing involves saving the computations already finished. This will be done directly in the recursive step.

We can move right onto the recursion. In our bottom-up recursive solution, we layer on the bigger numbers (locations further from our start) from the closer locations. The nested loop will allow us to build everything up-

for r in range(1, m):
            for c in range(1, n):
                numPaths[r][c] = numPaths[r - 1][c] + numPaths[r][c - 1]

And this is all we really need.

PS: I use recursive for an iterative solution. This is because mathematically- iteration is a primitive type of recursion. This video by Computerphile is a great introduction to this.

Step 4: Final Solution

Our final code looks like this-

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        numPaths = [[0 for _ in range(n)] for _ in range(m)]

        for r in range(m):
            numPaths[r][0] = 1

        for c in range(n):
            numPaths[0][c] = 1

        # dp[r][c] = number of unique paths to reach (r, c)
        for r in range(1, m):
            for c in range(1, n):
                numPaths[r][c] = numPaths[r - 1][c] + numPaths[r][c - 1]

        return numPaths[-1][-1] 

Time Complexity- O(n*m)

Space Complexity- O(n*m)

Loved the post? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.

Stay Woke,

Go kill all,

Devansh <3

Reach out to me on:

Small Snippets about Tech, AI and Machine Learning over here

Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

My content:

Read my articles: https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd