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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Unique Paths II and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →