Skip to main content

63. Unique Paths II

medium

Count distinct paths from top-left to bottom-right of an m x n grid where some cells are obstacles, moving only right or down. Extends Unique Paths with a single conditional in the recurrence.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m-1][n-1]). The robot can only move either down or right at any point in time. An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle. Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Constraints

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] is 0 or 1.
  • The answer is guaranteed to be less than or equal to 2 * 10^9.

Examples

Example 1

Input
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output
2

Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down. 2. Down -> Down -> Right -> Right.

Example 2

Input
obstacleGrid = [[0,1],[0,0]]
Output
1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Same recurrence as Unique Paths — except obstacles short-circuit to 0.

Hint 2

Initialize the first row and column carefully: once you hit an obstacle in row 0 or column 0, every cell after it in that row/column is 0.

Hint 3

For each non-obstacle inner cell: dp[i][j] = dp[i-1][j] + dp[i][j-1]. For obstacles: dp[i][j] = 0.

Solution approach

Reveal approach

Bottom-up DP. If the start or end is an obstacle, return 0. Initialize dp[0][0] = 1 if it is not an obstacle. For the first row and column, propagate 1 only while no obstacle has been seen — the first obstacle in row 0 or column 0 makes everything past it 0. For each inner cell, if it is an obstacle set dp[i][j] = 0, otherwise dp[i][j] = dp[i-1][j] + dp[i][j-1]. Return dp[m-1][n-1]. The first row and column rule is the only twist over Unique Paths. Space can be optimized to O(n) with a single rolling row.

Complexity

Time
O(m * n)
Space
O(n)

Related patterns

  • dynamic-programming
  • grid-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →