Unique Paths with Obstacles Explained: Tracing the 3x3 Grid

Imagine you are standing at the top-left corner of a 3x3 grid, looking down at the bottom-right destination. Without any obstacles, counting paths using combinatorics or straightforward addition is easy. But what happens when someone places a concrete boulder right in the middle? For our locked working example, let us define the grid as:

[[0, 0, 0],
[0, 1, 0],
[0, 0, 0]]

Here, 0 represents open terrain and 1 represents an impassable obstacle at coordinate $(1,1)$—the exact center. You are only allowed to move right or down.

If you blindly apply a naive formula that assumes an open grid, your calculation will happily route right through the boulder as if it were empty space. In reality, that boulder abruptly severs certain corridors, forcing traffic to bend outward. We need a systematic way to account for these obstacles without manually tracing every single pencil line on a napkin.

grid = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
]

To count every valid journey from the top-left corner to the bottom-right corner of our 3×3 grid [[0,0,0],[0,1,0],[0,0,0]], we need a mathematical model that breaks the grand journey down into local choices. At any free cell $(i,j)$, you could have arrived from the cell directly above it $(i-1,j)$ or the cell directly to its left $(i,j-1)$. Because our rules restrict movement strictly to right and down, there are no diagonal arrivals or backtracking loops.

This structural constraint turns a messy global routing puzzle into a clean recurrence relation. Let $DP[i][j]$ represent the total number of unique paths to reach cell $(i,j)$ from our starting position at $(0,0)$. If the current cell contains an obstacle (a value of 1), it acts as a permanent dead end, meaning $DP[i][j]=0$ because zero paths can pass through solid rock. If the cell is free (a value of 0), the total paths to get here is simply the sum of the paths coming from above plus the paths coming from the left: .

Let us apply this logic to our working example's center cell at $(1,1)$, which contains an obstacle (1). Even if paths could somehow flow into it, setting $DP[1][1]=0$ instantly quarantines the hazard, preventing any subsequent rightward or downward step from inheriting those dead routes. The outer boundaries also form natural walls: any cell in the first row can only be reached by moving continuously right, unless an obstacle blocks the corridor ahead.

To see our dynamic programming model in action, we compute the path counts cell by cell for our $3\times 3$ grid:

Given

- Start cell at $(0,0)$ with an initial path count of dp[0][0] = 1.
- The center obstacle at $(1,1)$ has value 1, making dp[1][1] = 0.

Steps

- dp[0][0] = 1
- dp[0][1] = dp[0][0] + 0 = 1 (moving right)
- dp[0][2] = dp[0][1] + 0 = 1 (moving right)
- dp[1][0] = dp[0][0] + 0 = 1 (moving down)
- dp[2][0] = dp[1][0] + 0 = 1 (moving down)

- For $(1,1)$, the cell is blocked (grid[1][1] == 1), so dp[1][1] = 0.
- For $(1,2)$, dp[1][2] = dp[0][2] + dp[1][1] = 1 + 0 = 1.

- For $(2,1)$, dp[2][1] = dp[1][1] + dp[2][0] = 0 + 1 = 1.
- For $(2,2)$ (the destination), dp[2][2] = dp[1][2] + dp[2][1] = 1 + 1 = 2.

Result

The complete DP table is:

[[1, 1, 1],
[1, 0, 1],
[1, 1, 2]]

The total number of unique paths to the bottom-right corner is 2.

Try this: Given the intermediate table row dp[1] = [1, 0, 1], explain why dp[2][1] receives a value of 1 instead of 0 despite dp[1][1] being an obstacle.

In our previous trace on the $3\times 3$ grid [[0,0,0],[0,1,0],[0,0,0]], the single obstacle at grid[1][1] forced the center cell's path count to 0 and left us with exactly 2 valid paths. But what happens if we shift the hazard just one step to the right into the bottom-right quadrant? Let us test your mental model of state transitions and zeroed-out paths before looking at the final deduction.

Consider a modified $3\times 3$ grid where the obstacle moves from the center grid[1][1] to grid[1][2], making our input [[0,0,0],[0,0,1],[0,0,0]].

Trace through the dynamic programming table row by row for this new grid. Keep in mind that any cell with an obstacle (1) immediately receives 0 paths, and any cell whose top and left ancestors are both blocked or zeroed will also cascade to 0.

- What is the path count at dp[1][2] (the obstacle cell)?
- What is the final path count at dp[2][2] (the bottom-right destination)?

# Modified 3x3 grid with obstacle shifted to grid[1][2]
grid = [
    [0, 0, 0],
    [0, 0, 1],
    [0, 0, 0]
]

# Question: How many unique paths exist from (0,0) to (2,2)?
# Write down or mentally trace the dp table values for row 1 and row 2.

Now that you have traced the 3x3 grid with its center hazard at [1][1] yielding exactly 2 unique paths, let us transfer this exact dynamic programming mental model to a larger or differently constrained environment.

Recall the fundamental recurrence relation that governed our work:

When scaling this logic to an $m\times n$ grid, the size of the board changes, but the local constraint propagation remains identical. Every cell is still strictly a function of its immediate northern and western precursors. If you encounter a labyrinth where obstacles form continuous walls (such as a vertical barrier splitting the grid in half), the accumulation of paths halts entirely along that boundary, starving any destination downstream.

To apply this effectively in code or design, always ensure your boundary conditions (the first row and first column) properly stop propagating paths the moment a single 1 appears. From there, the two-dimensional state transition handles the rest, whether the grid is $3\times 3$, $100\times 100$, or irregular in shape.

def uniquePathsWithObstacles(grid: list[list[int]]) -> int:
    # Apply your transfer knowledge here
    pass