62. Unique Paths

Leetcode #: 62
Name: Unique Paths
Difficulty: Medium
Url: https://leetcode.com/problems/unique-paths/

Prompt

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

Approach

You’re given a m x n grid and a robot is 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]) and can only move either down or right.

Your task is to return the number of possible unique paths that the robot can take to reach the bottom-right corner. It’s also important to note that the test cases are generated so that the answer will be less than or equal to 2 * 10⁹; therefore, we’ll want to use an optimized approach as opposed to a simple Brute-Force approach.

Stemming from an optimized approach, we’re dealing with a 2-D array or grid, we’ll want to implement 2-Dimensional Dynamic Programming.

There are 2 ways in which we can solve this problem utilizing Dynamic Programming:

1. Top-Down Dynamic Programming
2. Bottom-Up Dynamic Programming

Generally speaking, it’s a bit more difficult to come up with the Bottom-Up solution unless if you have a firm understanding of the Top-Down solution. Thus, I’ll be elaborating on the Top-Down approach.

The specific technique within Top-Down Dynamic Programming that we will use is called Memoization. The Top-Down approach utilizes recursion, and the technique Memoization implements caching where we’ll save the subproblems that we solve into the auxiliary data structure (typically a Hash Map or a dynamic array) as the stack frames within the call stack pop or bubbles back up the call stack. We can then retrieve or access what those subproblems that we have saved into the cache equate to when we encounter them again throughout the recursion tree.

For our recursive function, we’ll be needing 3 base cases:

1. We’ll want to check if the row or column of the subproblem is equal to the length of the total # of rows or columns respectively. If this is the case, then we know we can return 0 indicating there are no valid paths that can be formed because we are out-of-bounds.
2. We’ll want to index into our cache or auxiliary data structure at the specific row then specific column of the subproblem and check if it’s greater than 0. If so, we’ll want to return the value of the cache at that specific row and column.
3. Lastly, we’ll want to check if the row and column of the subproblem is equal to the total # of rows and columns-1 or in other words, the last row and column indicating that we’re at our destination position within the grid. If we are at this position, then we want to return 1 indicating that there is a valid path.

After specifying our base cases, we’ll want to cache into our auxiliary data structure at the specific row and column of our subproblem the sum of the 2 recursive calls of our function — the difference between the 2 recursive calls is that we would increment the row by 1 for one call and increment the column by 1 for the other call. This is because from the problem statement, we are informed that the robot can move either down (row + 1) or right (column + 1). Finally, we can return what we just cached into our auxiliary data structure, which we know is going to be the addition of our 2 recursive calls that I’ve mentioned earlier above.

Code

Python | Time: O(m * n) | Space: O(m * n)

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

Discord

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub