🦄62. Unique Paths

Medium | Grind 75 | March 10th Friday, 2023

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.

Constraints:

• 1 <= m, n <= 100

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

SOlUTION

At first, I found this problem challenging, but I later realized it was a classic DP problem. To solve it, we create a 2D array called DP, where each cell represents the number of unique ways to reach that cell from the starting position [0,0]. Since we can only move right or down, the top row and left column of the DP grid have only one unique path to reach their respective cells. For example, in a grid with 1 row and 3 columns, each cell has one possible unique path from the starting position. Similarly, in a grid with 5 rows and a single column, each cell also has only one possible unique path from the starting position.

However, in grids with more than one row and column, the problem becomes more complex. For a 2x2 grid, the number of unique ways to reach a cell is the sum of the unique ways to reach the cell above it and the cell to its left. We can only reach our desired cell through its left or top neighbors. Therefore, the possible unique paths to reach the desired cell are just the sum of the unique paths to reach the left(right movement) and top(downward movement) neighboring cells. This solution works because the unique way to reach any cell in the top row or leftmost column is always 1. We can build the rest of the grid using these two pieces of information.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # initialize a DP for size m by n 
        DP = [[1 for _ in range(n)] for _ in range(m)] 

        for row in range(1, m): 
            for col in range(1, n):
                # possible ways
                DP[row][col] = DP[row-1][col] + DP[row][col-1]
        
        return DP[m-1][n-1]

TIME AND SPACE COMPLEXITY

TIME: O(mn) where m is the number of rows and n is the number of columns. it takes O(nm) to initialize a DP of size m by n. Additionally, we iterate (m-1) * (n-1) times to build the DP. Therefore, the runtime is O(2mn).

SPACE: O(m*n). We build a DP of size m by n to store unique paths.

** Written with help from ChatGPT