Unique Paths II

Problem A robot starts at the top-left of an m x n grid and moves only right or down toward the bottom-right corner. Some cells are obstacles (1) and cannot be entered. Return the number of unique paths to the bottom-right.

Input / Output

• Input: int grid obstacleGrid (0 = free, 1 = obstacle).
• Output: number of obstacle-avoiding paths.

Constraints

• 1 <= m, n <= 100; answer fits in a 32-bit int per the classic constraints.

Example

• [[0,0,0],[0,1,0],[0,0,0]] → 2

Expected approach

• DP: paths(i,j) = 0 if obstacle, else paths(i-1,j) + paths(i,j-1); first row/column propagate 1 until the first obstacle, 0 after. O(m*n) time; O(n) space with a rolling 1-D array. Edge cases: obstacle at start or end → 0.