Journal Archive

2022

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    let n = obstacleGrid[0].length;
    let m = obstacleGrid.length;
    // edge case 
    if(obstacleGrid[0][0] === 1) return 0;
    
    const dpGrid = Array.from(Array(m), () => []);
    let obstacleSeen = false;
    // fill top row boundary
    for (let c = 0; c < n; c++) {
        if (obstacleSeen || obstacleGrid[0][c] === 1) {
            obstacleSeen = true;
            dpGrid[0][c] = 0;
        } else {
            dpGrid[0][c] = 1;
        }
    }
    
    obstacleSeen = false;
    // fill left column boundary
    for (let r = 0; r < m; r++) {
        if (obstacleSeen || obstacleGrid[r][0] === 1) {
            obstacleSeen = true;
            dpGrid[r][0] = 0;
        } else {
            dpGrid[r][0] = 1;
        }
    }
    
    // fill all the other cells 
    for (let i = 1; i < m; i++) {
        for(let j = 1; j < n; j++) {
            if (obstacleGrid[i][j] === 1) {
                dpGrid[i][j] = 0;
            } else {
                dpGrid[i][j] = dpGrid[i-1][j] + dpGrid[i][j-1];
            }
        }
    }
    
    return dpGrid[m-1][n-1];
};

Day 58: Solving one of LeetCode problems

63. Unique Paths II Difficulty - Medium

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