Unique Paths II medium

Problem Statement

You are given an m x n integer array obstacleGrid where obstacleGrid[i][j] equals 0 if an obstacle is present and 1 otherwise. A robot is located at the top-left corner obstacleGrid[0][0]. The robot can move either down or right at any point in time. The robot cannot pass through an obstacle. Return the number of possible unique paths that the robot can take to reach the bottom-right corner. The robot is initially located at the top-left corner obstacleGrid[0][0].

If there is no path, return 0.

Example 1:

Input: obstacleGrid = [[0,1],[1,0]] Output: 0 Explanation: There is an obstacle in the way.

Example 2:

Input: obstacleGrid = [[0,0],[0,0]] Output: 0 Explanation: There is an obstacle in the way at the start.

Steps

1. Initialization: Create a DP table (2D array) of the same dimensions as obstacleGrid, initialized with all zeros. This table will store the number of paths to reach each cell.

2. Base Case:

   • If obstacleGrid[0][0] is an obstacle (0), there are no paths, so return 0.
   • Otherwise, set dp[0][0] = 1 because there's one way to reach the starting cell (itself).

3. Handle Obstacles: Set dp[i][j] = 0 for any cell (i, j) that contains an obstacle (obstacleGrid[i][j] == 0).

4. Iterate and Fill DP Table: Iterate through the DP table, starting from cell (1, 0) and (0, 1). For each cell (i, j), its value is the sum of the number of paths to reach the cell above it (dp[i-1][j]) and the cell to its left (dp[i][j-1]). Remember to only consider valid cells (within the bounds of the grid).

5. Return Result: The value at dp[m-1][n-1] will be the number of unique paths to the bottom-right cell.

Explanation

The dynamic programming approach efficiently avoids recomputation by storing the number of paths to reach each cell. We build up the solution from the start, using the principle that the number of paths to a cell is the sum of the paths from the cell above and the cell to the left. Obstacles are handled by setting the corresponding DP cell to 0, effectively blocking paths that go through that cell.

Code

function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;

    // Create DP table and initialize with zeros
    const dp: number[][] = Array.from({ length: m }, () => Array(n).fill(0));

    // Base case: Check for obstacle at the starting point
    if (obstacleGrid[0][0] === 0) {
        return 0;
    } else {
        dp[0][0] = 1;
    }

    // Handle obstacles and fill DP table
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (obstacleGrid[i][j] === 0) {
                dp[i][j] = 0; // Obstacle blocks the path
                continue;
            }

            if (i > 0) {
                dp[i][j] += dp[i - 1][j];
            }
            if (j > 0) {
                dp[i][j] += dp[i][j - 1];
            }
        }
    }

    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), to store the DP table. We can optimize this to O(min(m, n)) using a 1D DP array if needed, but the 2D approach is more readable.