63. Unique Paths II

Unique Paths II

Problem Description

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 down or right at any 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 the robot can take to reach the bottom-right corner.

The test cases 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.

Approach) Iterative

var uniquePathsWithObstacles = function (obstacleGrid) {
  for (let i = obstacleGrid.length - 1; i >= 0; i--) {
    for (let j = obstacleGrid[i].length - 1; j >= 0; j--) {
      if (i === obstacleGrid.length - 1 && j === obstacleGrid[i].length - 1) {
        obstacleGrid[i][j] = obstacleGrid[i][j] === 1 ? 0 : 1;
        continue;
      }

      if (obstacleGrid[i][j] === 1) {
        obstacleGrid[i][j] = 0;
        continue;
      }

      if (i === obstacleGrid.length - 1) {
        obstacleGrid[i][j] = obstacleGrid[i][j + 1];
        continue;
      }

      if (j === obstacleGrid[i].length - 1) {
        obstacleGrid[i][j] = obstacleGrid[i + 1][j];
        continue;
      }

      obstacleGrid[i][j] = obstacleGrid[i + 1][j] + obstacleGrid[i][j + 1];
    }
  }
  return obstacleGrid[0][0];
};

Approach) Memo

var uniquePathsWithObstacles = function(obstacleGrid) {

    // memo to store results when first computed to avoid redundant computations
    const memo = [];

    function computeNumberOfPaths(vpos, hpos) {
        
        // handle edge cases introduced by javascript's dynamically allocated arrays
        if (typeof memo[vpos] === 'undefined') memo[vpos] = [];
        if (typeof memo[vpos][hpos] === 'undefined') memo[vpos][hpos] = [];
        
        // we hit an obstactle, so do not contribute to sum any further
        // note that doing this before the base case handles inputs such as [[1]]
        if (obstacleGrid[vpos][hpos] === 1) return 0;
        
        // base case - we have hit the starting square which has only one path to it
        if (vpos === 0 && hpos === 0) return 1;
        
        // check to see if memo exists for position to save recomputing
        if (typeof memo[vpos][hpos] !== 'undefined' && memo[vpos][hpos] > 0) return memo[vpos][hpos];
        
        // compute paths to position recursively
        let sum = 0;
        if (vpos > 0) sum += arrayDfs(vpos - 1, hpos);
        if (hpos > 0) sum += arrayDfs(vpos, hpos - 1);
        
        // store number of paths to position in memo
        memo[vpos][hpos] = sum;
        
        // return the number of paths to this position
        return sum;
    }
    
    return arrayDfs(obstacleGrid.length - 1, obstacleGrid[0].length - 1);
};




Approach) Recursion

var uniquePathsWithObstacles = function(obstacleGrid) {
    const [R, C] = [obstacleGrid.length, obstacleGrid[0].length];
    const dp = new Array(R).fill(-1).map(() => new Array(C).fill(-1));
    
    function helper(r, c) {
        if (r === R || c === C || obstacleGrid[r][c] === 1) return 0;
        if (r === R - 1 && c === C - 1) return 1;
        if (dp[r][c] !== -1) return dp[r][c];
        
        return dp[r][c] = helper(r + 1, c) + helper(r, c + 1);
    }
    
    return helper(0, 0);
};

Approach) Dynamic Programming

var uniquePathsWithObstacles = function(obstacleGrid) {
    let uniquePaths = [];
    let obs = false;
    
    // below commnents are valid for first row and col only
    
    // key poin to note here is that if we found an obstacle
    // then we cannot move in that row or column at all
    // so indexes after the obstaces will have value 0
    // because we cannot reach them.
    
    for (let i = 0; i < obstacleGrid.length; i++) {
        uniquePaths[i] = [];
        
        if (!obs && obstacleGrid[i][0] == '1') {
            obs = true;
        }
        
        // if obstacle found earlier than we cannot move in that row or col
        // so there are 0 paths that lead there
        uniquePaths[i][0] = !obs ? 1 : 0;
    }
    
    obs = false
    for (let i = 0; i < obstacleGrid[0].length; i++) {
        if (!obs && obstacleGrid[0][i] == '1') {
            obs = true;
        }
        uniquePaths[0][i] = !obs ? 1 : 0;
    }
    
    
    for (let row = 1; row < obstacleGrid.length; row++) {
        for (let col = 1; col < obstacleGrid[row].length; col++) {
            
            if (obstacleGrid[row][col] == 1) {
                // if an obstacle found then there will be 0 ways in which we can travel to another point
                uniquePaths[row][col] = 0;
                
            } else {
                
                 uniquePaths[row][col] = uniquePaths[row][col-1] + uniquePaths[row-1][col];
            }
        }
    }
    return  uniquePaths[uniquePaths.length-1] [uniquePaths[0].length -1]
};

Approach) Depth First Search

var uniquePathsWithObstacles = function(obstacleGrid) {
    return dfs(obstacleGrid, {x:obstacleGrid.length-1, y:obstacleGrid[0].length-1});
};

const getNeighbor = (matrix, position) => {
    const { x, y } = position;
    const results = [];
    if(matrix[x][y]===1){
        return [];
    }
    if(x-1 >= 0 && matrix[x-1][y] !== 1){
        results.push({x: x-1, y});
    }
    if(y-1 >= 0 && matrix[x][y-1] !== 1){
        results.push({x, y: y-1});
    }
    return results;
}

const dfs = (matrix, position, cache = new Map()) => {
    const key = getCacheKey(position);
    if(cache.has(key)){
        return cache.get(key);
    }
    if(isEndPosition(position) && notObstacle(matrix, position)){
        cache.set(key, 1);
        return 1;
    }
    const nextSteps = getNeighbor(matrix, position);
    let sum = 0;
    for(var i=0; i<nextSteps.length; i++){
        const nextPosition = nextSteps[i];
        sum += dfs(matrix, nextPosition, cache);
    }
    cache.set(key, sum);
    return sum;
}

const isEndPosition = (position) => {
    return position.x === 0 && position.y === 0;
}

const notObstacle = (matrix, position) => {
    return matrix[position.x][position.y] === 0;
}

const getCacheKey = (position) => {
    return `${position.x}-${position.y}`;
}

Conclusion

That’s all folks! In this post, we solved LeetCode problem 63. Unique Paths II

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!