Unique Paths II

Problem

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and space is marked as 1 and 0 respectively in the grid.

 

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.

Solution

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    const dp = Array(m + 1)
        .fill(null)
        .map(() => Array(n + 1).fill(0));

    dp[0][1] = 1;

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (!obstacleGrid[i - 1][j - 1]) { // current cell is not an obstacle
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
    }
    return dp[m][n];
};

We will implement a DP solution. Let dp[i][j] be the number of unique paths to reach the bottom-right corner of the grid obstacleGrid[0:i][0:j].

• For the base case, if i = 0 or j = 0, then dp[i][j] = 0 except for dp[0][1] = 1 (setting it this way makes things work out nicely).
• For the recursive case:
  • If the current cell we are on is an obstacle (ie. 1), then there is 0 ways to reach the cell.
  • Otherwise, the number of unique paths to reach the current cell is the total number of ways to reach the left and top cell.

Note that this base case might seem a little random and unintuitive. Another more intuitive set up is to let dp[i][j] be the number of unique paths to reach the bottom-right corner of the grid obstacleGrid[0:i + 1][0:j + 1]. In this case, the base case would instead be:

• If i = 0, then dp[0][j] = 1 until reaching an obstacle; after which, dp[0][j] = 0.
• If j = 0, then dp[i][0] = 1 until reaching an obstacle; after which, dp[i][0] = 0.

Optimization

We can optimize the above solution to use O(n) space as follows:

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    const n = obstacleGrid[0].length;
    const dp = Array(n).fill(0);

    dp[0] = 1;

    for (const row of obstacleGrid) {
        for (let i = 0; i <= n; i++) {
            if (row[i]) { // current cell is an obstacle
                dp[i] = 0;
            } else { // current cell is not an obstacle
                dp[i] += dp[i - 1] ?? 0;
            }
        }
    }
    return dp[n - 1];
};

Notice that in our original solution, only the direct previous row and col of dp are used for each new [i][j] entry. Thus, we can reduce our 2D dp array down to an 1D dp array to conserve space.