Leetcode 63. Unique Paths II

 63. Unique Paths II

Medium, Dynamic Programming

You are given an m x n integer array grid. There is a robot 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.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 109.

 

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

 

Constraints:

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1.

The problem Unique Paths II is a variation of the classic Unique Paths problem, where obstacles are placed on the grid. The robot can only move right or down, and it cannot move through obstacles. The goal is to count how many unique paths exist from the top-left corner to the bottom-right corner.

Approach 1: Dynamic Programming

Explanation:

We can solve this problem using dynamic programming by maintaining a DP table (dp) where dp[i][j] represents the number of unique paths to reach the cell (i, j) from the top-left corner.

The steps are as follows:

1. Initialization:

   • If the starting cell grid[0][0] is an obstacle (1), we can't start, so return 0.
   • If grid[0][0] is not an obstacle, initialize dp[0][0] = 1 since there is one way to be at the start.

2. Filling the DP table:

   • For each cell (i, j), the number of ways to reach it depends on the cell above it (dp[i-1][j]) and the cell to the left of it (dp[i][j-1]).
   • If grid[i][j] is an obstacle (1), set dp[i][j] = 0 because no path can pass through obstacles.
   • If grid[i][j] is not an obstacle (0), calculate dp[i][j] by summing the values from the cell above it and the cell to the left of it, i.e.:

     dp[i][j] = dp[i-1][j] + dp[i][j-1]
     

3. Boundary conditions:

   • For the first row (i = 0), if there's no obstacle, dp[0][j] = dp[0][j-1] (i.e., we can only move right).
   • For the first column (j = 0), if there's no obstacle, dp[i][0] = dp[i-1][0] (i.e., we can only move down).

4. Final result:

   • The value at dp[m-1][n-1] will be the number of unique paths from the top-left corner to the bottom-right corner.

Code:

public class Solution {
    public int UniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.Length;
        int n = obstacleGrid[0].Length;
        
        // Edge case: if the starting cell or the ending cell is an obstacle
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
            return 0;
        }
        
        int[,] dp = new int[m, n];
        
        // Initialize the starting cell
        dp[0, 0] = 1;
        
        // Fill the first row (can only come from the left)
        for (int j = 1; j < n; j++) {
            dp[0, j] = (obstacleGrid[0][j] == 1) ? 0 : dp[0, j - 1];
        }
        
        // Fill the first column (can only come from above)
        for (int i = 1; i < m; i++) {
            dp[i, 0] = (obstacleGrid[i][0] == 1) ? 0 : dp[i - 1, 0];
        }
        
        // Fill the rest of the dp table
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i, j] = 0; // No path through obstacle
                } else {
                    dp[i, j] = dp[i - 1, j] + dp[i, j - 1]; // Sum paths from above and left
                }
            }
        }
        
        // The bottom-right corner will contain the number of unique paths
        return dp[m - 1, n - 1];
    }
}

Time Complexity:

• Time Complexity: $O(m \times n)$, because we iterate over the grid and fill the DP table.
• Space Complexity: $O(m \times n)$, because we use a 2D DP array to store intermediate results.

---

Approach 2: Space Optimization (Using 1D DP Array)

Explanation:

We can optimize the space complexity by using a single 1D array instead of a 2D array. Since each row only depends on the current and previous rows, we can reduce the space to $O(n)$ by reusing the 1D array to store intermediate results.

Steps:

1. Use a 1D array dp where dp[j] represents the number of unique paths to reach cell (i, j) in the current row.
2. Iterate through the grid, updating the dp array based on the current cell's value and the values from the previous row (dp[j]).

Code:

public class Solution {
    public int UniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.Length;
        int n = obstacleGrid[0].Length;
        
        // Edge case: if the starting cell or the ending cell is an obstacle
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
            return 0;
        }
        
        int[] dp = new int[n];
        
        // Initialize the first cell
        dp[0] = 1;
        
        // Fill the dp array
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0; // If there's an obstacle, no paths to this cell
                } else if (j > 0) {
                    dp[j] += dp[j - 1]; // Add the number of paths from the left cell
                }
            }
        }
        
        // The last element in the dp array is the answer
        return dp[n - 1];
    }
}

Time Complexity:

• Time Complexity: $O(m \times n)$, because we still iterate over the grid but now use a 1D array.
• Space Complexity: $O(n)$, because we only use a 1D array to store the results for the current row.

---

Summary:

Approach	Time Complexity	Space Complexity	Explanation
Dynamic Programming (2D)	$O(m \times n)$	$O(m \times n)$	Uses a 2D DP table to store intermediate results.
Space Optimization (1D DP)	$O(m \times n)$	$O(n)$	Uses a 1D array for space optimization.

---

This problem is a great example of how we can optimize the solution space and make the solution more efficient by reducing memory usage.