Unique Paths II

Unique Paths II

What is this problem about?

The Unique Paths II interview question is a direct follow-up to the original grid navigation problem. In this version, the $m \times n$ grid contains obstacles, represented by 1s. The robot still starts at the top-left and aims for the bottom-right, but it cannot pass through any cell that contains an obstacle. Your task is to find the total number of unique paths that avoid all blocked cells.

Why is this asked in interviews?

This Unique Paths II coding problem is a staple at companies like Apple, Atlassian, and Nvidia. It tests whether a candidate can adapt a known algorithm (Unique Paths) to handle additional constraints. It evaluates your ability to handle edge cases, such as an obstacle being at the starting point or the destination, which would make the total path count zero.

Algorithmic pattern used

The primary Array, Matrix, Dynamic Programming interview pattern used here is an iterative approach. You maintain a DP table (or reuse the input grid to save space) where dp[i][j] stores the number of ways to reach that cell. The rule is simple: if grid[i][j] is an obstacle, dp[i][j] = 0. Otherwise, dp[i][j] = dp[i-1][j] + dp[i][j-1]. You must be careful to initialize the first row and column correctly, as an obstacle in the first row blocks all subsequent cells in that row.

Example explanation

Consider a $3 \times 3$ grid with an obstacle at the center (1, 1).

1. Initialize the first row: [1, 1, 1].
2. First column: [1, 1, 1].
3. Fill row 1:
   • Cell (1, 0) is 1.
   • Cell (1, 1) is an obstacle, so it's 0.
   • Cell (1, 2) is dp[0][2] + dp[1][1] = 1 + 0 = 1.
4. Fill row 2:
   • Cell (2, 0) is 1.
   • Cell (2, 1) is dp[1][1] + dp[2][0] = 0 + 1 = 1.
   • Cell (2, 2) is dp[1][2] + dp[2][1] = 1 + 1 = 2. Total unique paths: 2.

Common mistakes candidates make

A common error is not checking the start and end cells for obstacles before beginning the DP process. If the start is blocked, the answer is always 0. Another mistake is incorrectly handling the initialization of the first row and column; if a cell in the first row is an obstacle, all cells to its right should be 0, not 1.

Interview preparation tip

When you see a problem that is a variation of a classic one, focus on the "delta"—what has changed? In this case, the change is the obstacle condition. Always practice state-space reduction, such as using a 1D array instead of a 2D matrix to solve grid DP problems more space-efficiently.