Unique Paths II medium

Problem Statement

You are given an m x n integer array obstacleGrid where each cell is either empty (represented by a 0) or an obstacle (represented by a 1).

A robot is located at the top-left corner of the grid (i.e., obstacleGrid[0][0]). The robot tries to move to the bottom-right corner. The robot can only move either down or right at any point in time.

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

If there is an obstacle in the way, the robot cannot pass through that cell.

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, thus there are only two ways to reach the bottom-right corner from the top-left corner.

Example 2:

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

Steps and Explanation

This problem can be solved using dynamic programming. We create a DP table of the same size as the input grid. Each cell dp[i][j] will store the number of unique paths to reach that cell from the top-left corner.

1. Initialization:

   • If obstacleGrid[0][0] is 1 (obstacle), there are 0 paths. Otherwise, dp[0][0] = 1.
   • The first row and first column are initialized based on obstacles. If we encounter an obstacle, the number of paths to reach subsequent cells in that row/column becomes 0. Otherwise, it inherits the path count from the previous cell.

2. Iteration:

   • We iterate through the DP table from top-left to bottom-right.
   • For each cell dp[i][j], if it's an obstacle (obstacleGrid[i][j] == 1), we set dp[i][j] = 0.
   • Otherwise, the number of paths to reach dp[i][j] is the sum of paths from the cell above (dp[i-1][j]) and the cell to the left (dp[i][j-1]). This represents the robot moving down or right.

3. Result:

   • The final value dp[m-1][n-1] contains the total number of unique paths to reach the bottom-right corner.

Code

public class Solution {
    public int UniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.Length;
        int n = obstacleGrid[0].Length;

        // Create DP table
        int[,] dp = new int[m, n];

        // Initialize DP table
        if (obstacleGrid[0][0] == 0) {
            dp[0, 0] = 1;
        } else {
            return 0; // No path if starting point is blocked
        }

        // Initialize first row and column
        for (int i = 1; i < m; i++) {
            dp[i, 0] = (obstacleGrid[i][0] == 0) ? dp[i - 1, 0] : 0;
        }
        for (int j = 1; j < n; j++) {
            dp[0, j] = (obstacleGrid[0][j] == 0) ? dp[0, j - 1] : 0;
        }

        // Iterate and fill DP table
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
                } else {
                    dp[i, j] = 0;
                }
            }
        }

        // Return the result
        return dp[m - 1, n - 1];
    }
}

Complexity

• Time Complexity: O(m*n), where 'm' and 'n' are the dimensions of the grid. We iterate through the DP table once.
• Space Complexity: O(m*n), due to the DP table. We could optimize this to O(min(m,n)) by using only a 1D array if needed, but for clarity, the 2D array is used here.