Unique Paths II
A robot is at the top-left corner of an $m \times n$ grid. This time, there are obstacles in the grid. How many unique paths are there to the bottom-right corner? Use DP.
Why Interviewers Ask This
Airbnb asks this variation of the classic grid problem to assess a candidate's ability to adapt standard dynamic programming patterns to real-world constraints. They specifically evaluate how you handle edge cases, such as obstacles blocking the start or end points, and whether you can optimize space complexity while maintaining code clarity for scalable travel platform logic.
How to Answer This Question
1. Clarify Constraints: Immediately confirm if the robot starts or ends on an obstacle, which would make the answer zero. 2. Define State: Propose a DP table where dp[i][j] represents unique paths to cell (i, j). 3. Formulate Recurrence: Explain that normally paths equal sum of top and left neighbors, but here, if grid[i][j] is an obstacle, dp[i][j] becomes zero. 4. Handle Initialization: Detail setting the first row and column, stopping propagation immediately upon hitting an obstacle in either direction. 5. Optimize Space: Suggest reducing the 2D array to a 1D array since current values only depend on the previous row. 6. Code Structure: Write clean loops with early returns for invalid inputs before implementing the core logic.
Key Points to Cover
- Explicitly checking if the start or end cell is an obstacle
- Setting the DP value to zero when an obstacle is encountered
- Correctly breaking the initialization loop for the first row and column upon hitting an obstacle
- Explaining the transition from 2D to 1D space optimization
- Handling boundary conditions gracefully without index out of bounds errors
Sample Answer
To solve Unique Paths II, I first validate the input. If the starting point or destination contains an obstacle, we return zero immediately since no path exists. Next, I initialize a dynamic programming table with dimensions matching the grid. The recurrence relation is straightforward: the number of ways to reach any cell is the sum of ways to reach the cell directly above it and the cell to its left. However, the critical twist here is handling obstacles. If a cell contains a 1, representing an obstacle, the value at that position in our DP table must be set to zero, effectively blocking any path through it. When initializing the first row and column, I iterate through until I hit an obstacle; once encountered, all subsequent cells in that line remain zero because the path is blocked. After populating the table using nested loops, the bottom-right corner holds our answer. For optimization, I would mention that since we only need the previous row to calculate the current one, we can reduce space complexity from O(m*n) to O(n) by using a single array. This approach ensures we efficiently handle Airbnb's potentially large map data without unnecessary memory overhead.
Common Mistakes to Avoid
- Forgetting to reset the DP value to zero when an obstacle is found instead of skipping the calculation
- Initializing the first row/column incorrectly by not stopping propagation after the first obstacle
- Failing to check if the starting cell itself is an obstacle, leading to incorrect non-zero results
- Ignoring space optimization opportunities despite the problem being solvable with linear extra space
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.