The problem. Like Unique Paths, but some cells hold an obstacle (1 in obstacleGrid) that the robot can't enter. Count the paths from the top-left to the bottom-right moving only right or down.
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] -> 2
obstacleGrid = [[0,1],[0,0]] -> 1
obstacleGrid = [[1]] -> 0 (the start is blocked)Same recurrence as Unique Paths — paths from above plus paths from the left — with one rule: a blocked cell has 0 paths. That also fixes the edges automatically: along the top row, once a cell is blocked, every cell after it has 0 paths, because the only way in was through the obstacle. If the start itself is blocked, the answer is 0.
function uniquePathsWithObstacles(grid) { const m = grid.length, n = grid[0].length; const memo = new Map(); const paths = (r, c) => { if (r < 0 || c < 0 || grid[r][c] === 1) return 0; // off the grid or blocked if (r === 0 && c === 0) return 1; const key = r * n + c; if (!memo.has(key)) memo.set(key, paths(r - 1, c) + paths(r, c - 1)); return memo.get(key); }; return paths(m - 1, n - 1);}Time O(m · n), space O(m · n).
Open cells add the paths from above and from the left; blocked cells stay at 0.
function uniquePathsWithObstacles(grid) { const m = grid.length, n = grid[0].length; const paths = Array.from({ length: m }, () => new Array(n).fill(0)); for (let r = 0; r < m; r++) { for (let c = 0; c < n; c++) { if (grid[r][c] === 1) continue; // blocked: 0 paths if (r === 0 && c === 0) { paths[r][c] = 1; continue; } paths[r][c] = (r > 0 ? paths[r - 1][c] : 0) + (c > 0 ? paths[r][c - 1] : 0); // above + left } } return paths[m - 1][n - 1];}Time O(m · n), space O(m · n).
function uniquePathsWithObstacles(grid) { const n = grid[0].length; const row = new Array(n).fill(0); row[0] = 1; // the start (if open) for (const cells of grid) { for (let c = 0; c < n; c++) { if (cells[c] === 1) row[c] = 0; // blocked else if (c > 0) row[c] += row[c - 1]; // above (old row[c]) + left } } return row[n - 1];}Time O(m · n), space O(n). A blocked start sets row[0] = 0 on the first row, and it stays 0.
