Unique Paths II (Obstacles)

MediumDynamic Programminggrid DP

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A robot stands in the top-left cell of an m x n grid and wants to reach the bottom-right cell. On each step the robot may move only **one cell to the right** or **one cell down**. Some cells contain obstacles that the robot cannot enter. The grid is given as a 2D integer array grid, where: - grid[i][j] == 0 means the cell is open. - grid[i][j] == 1 means the cell holds an obstacle. Return the number of distinct paths the robot can take from the top-left cell to the bottom-right cell while avoiding every obstacle. If the start cell or the destination cell itself contains an obstacle, no valid path exists and the answer is 0. The number of paths is guaranteed to fit in a 32-bit signed integer.

Examples

Input: grid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
There is a single obstacle in the center of the 3x3 grid. The two ways around it are: right -> right -> down -> down, and down -> down -> right -> right.
Input: grid = [[0,1],[0,0]]
Output: 1
The only way is down then right; moving right first lands on the obstacle.
Input: grid = [[1]]
Output: 0
The single start cell is an obstacle, so the robot cannot even begin.

Constraints

  • `m == grid.length`
  • `n == grid[i].length`
  • `1 <= m, n <= 100`
  • `grid[i][j]` is either `0` or `1`
  • The answer fits in a 32-bit signed integer.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More grid DP problems