DSA interview question

Unique Paths II (With Obstacles)

Medium · Algorithms · Topics: dynamic programming, matrix

The problem

You're building a warehouse robot navigation simulator. A robot starts at the top-left corner of an m x n warehouse grid and needs to reach the bottom-right corner to pick up a package. The robot can only move right or down at each step. Some cells contain shelving units (obstacles) that the robot cannot pass through. Your task: compute the number of distinct paths the robot can take from start to destination, avoiding all obstacles.

Example: grid 0 0 0 0 1 0 0 0 0 (1 = obstacle, 0 = free cell) → there are 2 unique paths avoiding the obstacle in the middle.

Function signature

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid);

Test cases

Input `obstacleGrid`	Output	Explanation
`[[0,0,0],[0,1,0],[0,0,0]]`	2	Two paths around the middle obstacle
`[[0,1],[0,0]]`	1	Only one path: down, down, right (obstacle blocks top-right)
`[[1,0]]`	0	Start cell itself is an obstacle → no paths possible
`[[0]]`	1	Single free cell, start = end, one trivial path
`[[1]]`	0	Single cell that is an obstacle → no paths
`[[0,0],[1,1],[0,0]]`	0	Entire middle row blocked → impossible to reach bottom
`[[0,0,0]]`	1	Single row, no obstacles, one straight path

(Confirm: grid contains only 0s and 1s; if the start or end cell is itself an obstacle, answer is 0.)

How interviewers phrase it

"You have a grid where some cells are blocked. Starting from the top-left, moving only right or down, how many distinct ways are there to reach the bottom-right?"
This is a direct follow-up to the classic Unique Paths (LeetCode 62) problem — interviewers often start with the obstacle-free version, then add obstacles as a twist (LeetCode 63).
May be phrased as "robot path counting with blocked cells" or "count paths in a grid avoiding walls."

Clarifying questions to ask

What do the grid values represent exactly — is 1 an obstacle and 0 a free cell, or could it be reversed? Confirm the convention.
What if the start cell or the end cell itself is an obstacle? (Answer should be 0 in that case — confirm this expectation.)
Can the robot move only right and down, or are other directions (up, left) allowed? (This problem: right/down only.)
Should the count be returned as a plain integer, or could path counts be large enough to require modulo arithmetic or a larger data type (e.g., long long)?
Are m and n guaranteed to be at least 1, i.e., is an empty grid a possibility I need to handle?

Follow-ups to expect

"Can you solve it with O(1) extra space (in-place)?"
"What if the number of paths can be extremely large and overflow?"
"What if diagonal moves were also allowed?"
"Can you also return one example of an actual valid path, not just the count?"
"What if obstacles could be dynamically added/removed and you need repeated queries?"
"How does this compare to the version without obstacles (Unique Paths I)?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview