Unique Paths II

The key idea

The number of ways to reach a cell equals the ways to reach the cell above it plus the ways to reach the cell to its left, because the robot can only arrive from those two directions. An obstacle cell is unreachable, so its count is forced to 0, which naturally cancels any path that would have crossed it.

Problem

You are given an m x n integer array obstacleGrid. A robot starts at the top-left corner (grid[0][0]) and wants to reach the bottom-right corner. The robot can only move either down or right at any point in time.

An obstacle and an empty space are marked as 1 and 0 respectively in obstacleGrid. 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.

The testcases are generated so that the answer will be less than or equal to 2 * 10^9.

Constraints

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] is 0 or 1

Examples

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

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

Complexity

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

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →