Problems/63. Unique Paths II

63. Unique Paths II

MediumMatrixDynamic ProgrammingDP

You are given an m x n integer array grid. An obstacle and space are marked as 1 and 0 respectively in the grid.

A robot is 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. Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Example 1

Input: grid = [ [0, 0, 0], [0, 1, 0], [0, 0, 0] ]

Output: 2

There is one obstacle in the middle. The two unique paths are: 1. Right -> Right -> Down -> Down, 2. Down -> Down -> Right -> Right.

Example 2

Input: grid = [ [0, 1], [0, 0] ]

Output: 1

The top-right cell is blocked. The only valid path is (0,0) -> (1,0) -> (1,1).

Example 3

Input: grid = [ [1, 0], [0, 0] ]

Output: 0

The starting position itself is blocked, so no paths are possible.

Visualizer

⌥

Visualizer will appear here