Dynamic Programming • 2D Grids

Unique Paths II

Find the number of unique paths from the top-left to the bottom-right of a grid, but this time, the grid contains obstacles that block your path.

Try Interactive Simulator

Overview

This is a variation of "Unique Paths". The core logic remains the same: the number of ways to reach a cell is the sum of ways to reach the cell above it and the cell to its left.

The Obstacle Rule

If a cell contains an obstacle (represented by `1`), you cannot step on it. Therefore, the number of ways to reach that specific cell is `0`.

Edge Initialization

When initializing the first row and column, if you hit an obstacle, all subsequent cells in that row/column must be `0` because they are permanently blocked.

Optimization

Just like Unique Paths, this can be optimized to `O(N)` space by only keeping track of the current row and the previous row, or even just a single 1D array.

0

X

0

Code Tracker

:::

1if (obstacleGrid[0][0] === 1) return 0;

2let dp = Array.from({ length: m }, () => new Array(n).fill(0));

3dp[0][0] = 1;

4// Initialize first col and row...

5for (let r = 1; r < m; r++) {

6 for (let c = 1; c < n; c++) {

7 if (obstacleGrid[r][c] === 1) {

8 dp[r][c] = 0;

9 } else {

10 dp[r][c] = dp[r-1][c] + dp[r][c-1];

11 }

12 }

13}

14return dp[m-1][n-1];

Unique Paths Ii

Unique Paths Ii

Unique Paths II

Overview

The Obstacle Rule

Edge Initialization

Optimization

Unique Paths II

Overview

The Obstacle Rule

Edge Initialization

Optimization