Problem 10 - Unique Paths

Explore our archive for previous posts.

Question

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.

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

The solution uses dynamic programming to calculate the number of unique paths from the top-left cell to the bottom-right cell in a grid. It initializes the first row and first column to 1 since there is only one way to reach them. Then, it iterates through the remaining cells, calculating the number of unique paths by summing up the paths from the above cell and left cell. Finally, it returns the number of unique paths for the bottom-right cell.

Here are the detailed steps:

1. Since there is only one way to reach any cell in the first row or first column (by moving either right or down), we set dp[0][j] = 1 and dp[i][0] = 1 for all valid i and j.

2. Then, for each cell dp[i][j], we calculate the number of unique paths by summing up the paths from the cell above (dp[i-1][j]) and the cell to the left (dp[i][j-1]) because we can only move down or right.

3. Finally, we return dp[m-1][n-1], which represents the number of unique paths to reach the bottom-right cell.

Solution

Solve it here

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        
        // Initialize the first row and first column to 1 since there is only one way to reach them
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        
        // Calculate the number of unique paths for each cell by summing up the paths from the above cell and left cell
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        
        return dp[m-1][n-1];
    }
}

Time and space complexity

Time Complexity: The time complexity of the above solution is O(M * N), where M and N are the number of rows and columns in the grid. This is because we iterate through each cell in the grid once to calculate the number of unique paths.

Space Complexity: The space complexity of the solution is also O(M * N), because we use a 2-D array of size M * N to store the intermediate results.