AlgoMaster Logo

Unique Paths II

mediumFrequency8 min readUpdated June 23, 2026

Understanding the Problem

This is an extension of the classic "Unique Paths" problem, with one change: some cells are blocked by obstacles. The robot still starts at the top-left and needs to reach the bottom-right, moving only right or down. Now any cell containing a 1 is impassable, and no valid path can go through it.

In the original problem, every cell was reachable and contributed paths from its top and left neighbors. An obstacle cell contributes zero paths. Any path that would have gone through that cell does not exist.

One edge case stands out: if the start cell (0, 0) or the destination cell (m-1, n-1) is itself an obstacle, the answer is 0. No path can begin at a wall, and no path can end at one.

Key Constraints:

  • 1 <= m, n <= 100: The grid has at most 10,000 cells, so an O(m * n) solution runs comfortably within limits.
  • The answer is at most 2 * 10^9. The 32-bit signed maximum is about 2.147 * 10^9, so the result fits in a 32-bit int. Every intermediate DP value is a partial path count no larger than the final answer, so a 32-bit int holds all running values without overflow.

Approach 1: Recursion (Brute Force)

Intuition

From any cell (i, j), the robot has two choices: go right to (i, j + 1) or go down to (i + 1, j). The number of paths from (i, j) to the destination is the sum of paths from those two neighbors. An obstacle cell returns 0, since no path can pass through it.

Recursion handles obstacles by treating them as dead ends in the recursion tree. It has the same flaw as the brute force for Unique Paths: it recomputes the same subproblems an exponential number of times.

Algorithm

  1. If the start cell (0, 0) or the destination cell (m-1, n-1) is an obstacle, return 0.
  2. Define a recursive function countPaths(i, j) that returns the number of paths from (i, j) to the bottom-right corner.
  3. Base case: if i == m - 1 and j == n - 1, return 1.
  4. If i >= m, j >= n, or the cell is an obstacle, return 0.
  5. Return countPaths(i + 1, j) + countPaths(i, j + 1).
  6. Call countPaths(0, 0).

Example Walkthrough

Input:

0
1
2
0
0
0
0
1
0
1
0
2
0
0
0
obstacleGrid

The recursion explores every move sequence from (0,0). Each call branches into a "down" call and a "right" call. Any branch that enters the obstacle at (1,1) returns 0, and any branch that walks off the grid returns 0. The branches that reach (2,2) each return 1. Two such branches survive: Right, Right, Down, Down and Down, Down, Right, Right. Their returns sum back up the tree to 1 + 1 = 2.

Code

The recursion recomputes the same cells repeatedly. There are only m * n distinct subproblems, but each one is solved many times. Building the answer bottom-up computes each cell exactly once.

Approach 2: Dynamic Programming (2D Table)

Intuition

Instead of recursing from the top-left and caching results, build the answer bottom-up with a 2D DP table. Define dp[i][j] as the number of unique paths from (0, 0) to cell (i, j). The recurrence matches the original Unique Paths problem:

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

With one modification: if obstacleGrid[i][j] == 1, then dp[i][j] = 0, since no path can end at an obstacle.

The first row and first column need separate handling. In the obstacle-free version, they're all 1s. An obstacle in the first row blocks every cell to its right, since the only way to reach those cells is by moving right from the start. An obstacle in the first column blocks every cell below it for the same reason.

Algorithm

  1. If the start cell or the destination cell is an obstacle, return 0.
  2. Create a 2D array dp of size m x n, initialized to 0.
  3. Fill the first column: set dp[i][0] = 1 for each row i until you hit an obstacle. Once you encounter an obstacle, all remaining cells below it stay 0.
  4. Fill the first row: set dp[0][j] = 1 for each column j until you hit an obstacle. Once you encounter an obstacle, all remaining cells to the right stay 0.
  5. For each cell (i, j) from (1, 1) to (m-1, n-1): if obstacle, set 0; otherwise, set dp[i][j] = dp[i - 1][j] + dp[i][j - 1].
  6. Return dp[m - 1][n - 1].

Example Walkthrough

1Initialize: first row and first column all 1s (no obstacles block them)
0
1
2
0
1
1
1
1
1
0
0
2
1
0
0
1/6

Code

The time complexity is optimal, but the DP table uses O(m * n) space. Filling row i only reads row i - 1, so a single 1D array updated in place as each row is processed reduces the space to O(n).

Approach 3: Dynamic Programming (Space Optimized)

Intuition

Computing dp[i][j] only needs dp[i-1][j] (directly above) and dp[i][j-1] (directly to the left). The computation never reads back more than one row, so a single 1D array of size n is enough.

Process the grid row by row. At the start of processing row i, the 1D array dp[j] holds the values from row i - 1. Sweeping left to right, each dp[j] is updated to become the value for row i:

  • dp[j] before its update equals dp[i-1][j] (the cell above).
  • dp[j-1] was already updated in this row, so it equals dp[i][j-1] (the cell to the left).

So dp[j] = dp[j] + dp[j-1] combines the top and left contributions. The left-to-right order is required: dp[j-1] must already hold the current row's value before dp[j] reads it, and dp[j] must still hold the previous row's value when read. When the cell is an obstacle, set dp[j] = 0.

Algorithm

  1. If the start cell or the destination cell is an obstacle, return 0.
  2. Create a 1D array dp of size n, initialized to 0.
  3. Initialize the first row: set dp[j] = 1 for each column j until you hit an obstacle.
  4. For each row i from 1 to m - 1:
    • If obstacleGrid[i][0] == 1, set dp[0] = 0. Otherwise, dp[0] retains its value.
    • For each column j from 1 to n - 1: if obstacle, set dp[j] = 0; otherwise, dp[j] = dp[j] + dp[j - 1].
  5. Return dp[n - 1].

Example Walkthrough

1Initialize dp (row 0): all 1s, no obstacles in first row
0
1
1
1
2
1
1/8

Code