Created
May 20, 2022 16:12
-
-
Save albertininm/43d573c25e8a1592265cfe44e5cf414d to your computer and use it in GitHub Desktop.
unique-paths-ii
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * @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; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment