Leetcode: Unique Paths II

This question is asked at Amazon and Bloomberg, and it is the more advanced version of the Unique Paths I question, which I posted here, and uses dynamic programming to figure out the number of paths it took to go from the top left corner to the bottom right in terms of the robot. 

The new question is as follows: 

A robot is located at the top-left corner of an m x n grid, and can only move either down or right at any point in time, trying to reach the bottom right corner of the grid. If there are some obstacles to the grids, how many unique paths would there be? 

Here are some examples of a robot with an obstacle in the middle and at the bottom right corner:

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.

And here is a description of the solution: 

The robot can only move either down or right, hence any cell in the first row can only be reached from the cell left to it, and any cell in the first column can only be reached from the cell above it. For any other cell on the grid, we can reach either it from the cell on the left or to the cell above it, and we won't let an obstacle cell contribute to it. This is a dynamic programming problem which uses an obstacle grid array. 

1. The base case is if the first cell of the obstacle grid at index [0,0] contains 1. This means there is an obstacle where the robot is; as a result, we always return 0. 

2. Else if the obstacleGrid[0, 0] has a 0 we set it to 1 and move ahead to iterate the first row and column. Set the 1 value of the the rows and columns of the cells to 0, because these won't affect any other cell, since there's obviously obstacles there. Now we iterate through an array and without obstacles we get the same as the previous problem linked, above take one row back and one column back with the same columns and rows, respectively, as follows: 

obstacleGrid[i, j] = obstacleGrid[i - 1][j] + obstacleGrid[i, j - 1] . Else set the value of [i,j] in the array to 0 if there is an obstacle at the specified point [i,j]. 

The space complexity is O(1) since the only space we are using here is the array. The time complexity is O(M x N) because we process each cell just once, with M rows and N columns. 

Now onto the Javascript code and explanation: 

Here's a top 2% quickness javascript solution:

/**

 * @param {number[][]} obstacleGrid

 * @return {number}

 */

var uniquePathsWithObstacles = function(obstacleGrid) {

    var R = obstacleGrid.length;

    var C = obstacleGrid[0].length;

    //base case if obstacle is in the space of robot

    if(obstacleGrid[0][0] == 1) return 0;

    //initialize since there is only one path to go and this is through {0,0} 

    obstacleGrid[0][0] = 1;

    //iterate through everything and set one path to move if there is a path from the previous row and column, respectively. 

    for(i = 1; i < R; i++) {

        if(obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1){

            obstacleGrid[i][0] = 1;

        } else {

            obstacleGrid[i][0] = 0;

        }

    }

    

    for(i = 1; i < C; i++) {

        if(obstacleGrid[0][i] == 0 && obstacleGrid[0][i - 1] == 1){

            obstacleGrid[0][i] = 1;

        } else {

            obstacleGrid[0][i] = 0;

        }

    }

    //finalizing everything with a dynamic programming solution, 

    //go add the paths from previous grid spaces or else have 0 paths in space that has an obstacle.

    for(i = 1; i < R; i++) {

        for(j = 1; j < C; j++) {

            if(obstacleGrid[i][j] == 0){

                obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];

            } else {

                obstacleGrid[i][j] = 0;

            }

        }

    }

    //return the last element of the array which is the point we want the robot to reach. 

    return obstacleGrid[R - 1][C - 1];

};