Categories
Array Dynamic Programming Leetcode

Unique Paths with Obstacles

let uniquePathsWithObstacles = function(obstacleGrid) {

if (!obstacleGrid || !obstacleGrid.length) return 0;

function markNextRowsAsZero(col) {
for (let i = col; i < maxCol; i++) {
obstacleGrid[0][i] = 0;
}
}
function markNextColumnsAsZero(row) {
for (let i = row; i < maxRow; i++) {
obstacleGrid[i][0] = 0;
}
}

let maxRow = obstacleGrid.length,
maxCol = obstacleGrid[0].length,
OBSTACLE = 1, VISITED = -1;

// first block is obstacle return 0;
if (obstacleGrid[0][0] === OBSTACLE) {
return 0;
}

// mark all first rows as either 1 or zero
for (let col = 0; col < maxCol;col++) {
if (obstacleGrid[0][col] === OBSTACLE) {
markNextRowsAsZero(col);
break;
}
else {
obstacleGrid[0][col] = 1;
}
}

// mark all first columns as either 1 or zero
for (let row = 1; row < maxRow;row++) {
if (obstacleGrid[row][0] === OBSTACLE) {
markNextColumnsAsZero(row);
break;
}
else {
obstacleGrid[row][0] = 1;
}
}

for (let row = 1; row < maxRow;row++) {
for (let col = 1; col < maxCol;col++) {
if (obstacleGrid[row][col] === OBSTACLE) {
obstacleGrid[row][col] = 0;
}
else {
obstacleGrid[row][col] =
obstacleGrid[row - 1][col] +
obstacleGrid[row][col - 1];
}

}
}

return obstacleGrid[maxRow - 1][maxCol - 1];
};

Leave a Reply

Your email address will not be published. Required fields are marked *