Unique Paths II

Avoid going through obstacle and return total number of ways to reach destination

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

Solution

Brute Force

var uniquePathsWithObstacles = function (obstacleGrid) {

    function recurr(i, j) {
        if (i < 0 || j < 0 || obstacleGrid[i][j] == 1) {
            return 0;
        }
        
        if (i == 0 && j == 0) {
            return 1;
        }

        let up = recurr(i - 1, j);
        let right = recurr(i, j - 1);

        return right + up;

    }
    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length

    return recurr(m - 1, n - 1)
};

Memorization

var uniquePathsWithObstacles = function (obstacleGrid) {

    function recurr(i, j,dp) {
        if (i < 0 || j < 0 || obstacleGrid[i][j] == 1) {
            return 0;
        }

        if (i == 0 && j == 0) {
            return 1;
        }

        if(dp[i][j] !==0){
            return dp[i][j]
        }
        let up = recurr(i - 1, j,dp);
        let right = recurr(i, j - 1,dp);
        dp[i][j]=right + up
        return dp[i][j];

    }
    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length

    let dp = Array.from({length:m}, ()=> Array(n).fill(0)) 

    dp[0][0]=1

    return recurr(m - 1, n - 1, dp)
};

Tabulation

var uniquePathsWithObstacles = function (obstacleGrid) {


    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length

    let dp = Array.from({ length: m }, () => Array(n).fill(0))

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[i][j] = 0;
                continue;
            }
            if (i == 0 && j == 0) {
                dp[0][0] = 1
                continue;
            }
            
            let up = 0

            let left = 0;

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

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

        }
    }

    return dp[m - 1][n - 1]
};