Unique paths II
MediumAn obstacle contributes zero paths
Problem
Count grid paths from top-left to bottom-right with obstacles blocking some cells.
Paths to a cell = paths from above + from the left, but an obstacle cell contributes 0.
The idea
The same additive recurrence, except a blocked cell has a count of zero and passes nothing on. That single rule propagates the blockage correctly with no extra logic.
The trick
- Set blocked cells to 0 before summing.
- An obstacle at the start or end makes the answer 0.
1
1
1
1
1
1
1
1
1
Step 1 of 6. Top row and left column have exactly 1 path. Every other cell = paths from above + from the left.
1/6
Optimal
timeO(n·m)spaceO(m)
Row-rolling sums.
1const row = Array(n).fill(1);2for (let i = 1; i < m; i++)3 for (let j = 1; j < n; j++)4 row[j] += row[j - 1];5return row[n - 1];Input
- grid
- 3 × 3
Memory
- at
- —
- cells marked
- 5
Output
- paths
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- grid = [[0,0,0],[0,1,0],[0,0,0]]
- Output:
- 2
- Explanation:
- The middle rock blocks some routes → 2.
Example 2
- Input:
- grid = [[0,1],[0,0]]
- Output:
- 1
- Explanation:
- Only one way around the obstacle.
Example 3
- Input:
- grid = [[1]]
- Output:
- 0
- Explanation:
- Start blocked → 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.