unique-paths-ii

index.js

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
 var uniquePathsWithObstacles = function(obstacleGrid) {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0].length;

  const numberOfValidPaths = new Array(m);

  for(let i = 0; i < m; i++) {
    numberOfValidPaths[i] = new Array(n).fill(0);
  }

  const ans = findNumberOfPaths(obstacleGrid, 0, 0, numberOfValidPaths);

  return ans;
};

const positions = [[0, 1], [1, 0]];

function findNumberOfPaths(grid, i, j, numberOfValidPaths) {
  const isInBound = i >=0 && i < grid.length && j >= 0 && j < grid[0].length;

  if(!isInBound) {
    return 0;
  }

  if(grid[i][j] === 1) {
    numberOfValidPaths[i][j] = false;
    return 0;
  }

  if(numberOfValidPaths[i][j] > 0) {
    return numberOfValidPaths[i][j];
  }

  if(i === grid.length - 1 && j === grid[0].length - 1) {
    return 1;
  }

  const ans = positions
                .map(([r, c]) => findNumberOfPaths(grid, i+r, j+c, numberOfValidPaths))
                .reduce((prev, curr) => prev+curr, 0);

  numberOfValidPaths[i][j] = ans;

  return ans;
}