🧩 Unique Paths II - When Reality Gets Messy

How to adapt your solution when constraints change: The obstacle challenge

SERIES NAVIGATION

📘 Unique Paths Series:

The Discovery Journey - How humans naturally discover the solution
Plain English Proof - Accessible logical reasoning
Formal Proof - Mathematical rigor and certainty
🧩 When Reality Gets Messy - Discovery (You are here) | Plain Proof | Formal Proof

THE PROBLEM (LC 63)

A robot is located at the top-left corner of an m × n grid. The robot can only move either down or right.

New Constraint: Now an obstacle and empty space are marked as 1 and 0 respectively in the grid.

Goal: How many possible unique paths are there to reach the bottom-right corner?

Key Difference: Some cells are now blocked and cannot be stepped on or passed through.

Example: If the center cell is blocked in a 3×3 grid → 2 unique paths (instead of 6)

🧠 Designer's Brain: The "Oh No" Moment

Your First Reaction When Seeing Obstacles

You've just mastered the clean, beautiful pattern from Unique Paths I:

1  1
2  3
3  6

Then the problem adds: "Oh, by the way, some cells have obstacles."

1  1
X  ?
?  ?

YOUR MENTAL PROCESS BREAKS

That cell with the X... you can't step on it. But wait, that means:

❌ You can't reach it (so it should have 0 paths)
❌ You can't pass THROUGH it to reach cells beyond it
❌ The beautiful addition formula dp[i][j] = dp[i-1][j] + dp[i][j-1] suddenly feels fragile

THE CRUCIAL MOMENT

Most people panic and think they need a completely different approach.

But let's think more carefully...

🤔 The Fundamental Question

What Actually Changes When We Add Obstacles?

Let's go back to our core insight from Unique Paths I:

Original insight: "To reach cell (i,j), I must have come from either (i-1,j) or (i,j-1), and I can count paths from both sources."

With obstacles, ask yourself: Does this insight still hold?

THE ANSWER

Yes, partially.

The logic doesn't break—it just needs one additional rule.

🔬 Discovery Process: Building Intuition

Experiment 1: What happens to an obstacle cell?

Imagine you're standing at the start, looking at your grid:

S  .  .
.  X  .
.  .  E

Questions:

Can you step on the X? No.
How many ways are there to reach the X? Zero.

FIRST RULE DISCOVERED

If a cell has an obstacle, dp[i][j] = 0.

But here's the deeper question: Why does this single rule fix everything?

Experiment 2: What happens to cells AFTER an obstacle?

Let's trace what happens to the cell at (1,2) — the one to the right of the obstacle:

1  1
X  ?
?  ?

Normally you'd calculate:

dp[1][2] = dp[0][2] + dp[1][1]

But dp[1][1] is an obstacle, so it equals 0.

Therefore:

dp[1][2] = 1 + 0 = 1

THE FORMULA STILL WORKS!

You're just adding zero from the blocked direction.

Let's continue to cell (2,2):

1  1
0  1
?  ?

For cell (2,1):

dp[2][1] = dp[1][1] + dp[2][0] = 0 + 1 = 1

For cell (2,2):

dp[2][2] = dp[1][2] + dp[2][1] = 1 + 1 = 2

The complete grid:

1  1
0  1
1  2

💡 The Critical Insight (What Makes This "Obvious")

Why does setting obstacle cells to 0 automatically handle everything?

DEEP PROPERTY: MATHEMATICAL PROPAGATION OF IMPOSSIBILITY

When you set an obstacle cell to 0, you're not just saying "I can't reach this cell."

You're encoding something more powerful: "This cell contributes NOTHING to any downstream calculations."

Think About It Algebraically

When you calculate:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

If one of those sources is an obstacle (with value 0), you get:

dp[i][j] = dp[i-1][j] + 0
// or
dp[i][j] = 0 + dp[i][j-1]

THE ZERO AS IDENTITY ELEMENT

The zero acts as an identity element for impossibility. It says:

"Ignore this direction; it contributes no paths."

The beautiful part: This propagates automatically through your entire grid. You don't need special logic to say "check if there's an obstacle somewhere in this path." The zeros handle it through normal arithmetic.

🎯 Deeper Understanding: Why Addition Still Works

The Partition Principle Revisited

Remember from Unique Paths I: we split all paths into "those coming from above" and "those coming from left."

With obstacles, this principle doesn't break—it just means one group might be empty:

THE THREE CASES

Case 1: Cell above is reachable, cell to left has obstacle

Group A (from above): Has some paths
Group B (from left): Empty (0 paths)
Total: Group A + 0

Case 2: Both neighbors are obstacles

Group A: Empty (0 paths)
Group B: Empty (0 paths)
Total: 0 + 0 = 0
Meaning: This cell is unreachable (an island)

Case 3: Both neighbors are reachable

Works exactly like Unique Paths I
Total: Group A + Group B

THE UNIVERSAL FORMULA

dp[i][j] = dp[i-1][j] + dp[i][j-1]

This formula is universal. It doesn't need modification. Only the initialization changes.

🚨 Edge Cases as Concept Validators

Edge 1: Start position has obstacle

X  .  .
.  .  .
.  .  E

If you can't even start, how many paths exist? Zero.

Does our logic handle this?

Yes: dp[0][0] = 0, and since all other cells depend on it, they all propagate to 0.

VALIDATES

Our obstacle handling works even at boundaries.

Edge 2: End position has obstacle

S  .  .
.  .  .
.  .  X

The destination is blocked. Answer: Zero paths.

Does our logic handle this?

Yes: We calculate normally until we reach the end, where we set dp[m-1][n-1] = 0.

VALIDATES

We don't need special "destination checking."

Edge 3: Obstacle creates an impossible barrier

S  X  .
.  X  .
.  X  E

The wall of obstacles cuts off all paths. Let's trace:

Row 0: [1, 0, 0]  // can't pass the first obstacle
Row 1: [1, 0, 0]  // blocked by obstacle above
Row 2: [1, 0, 0]  // blocked by obstacle above

Result: 0 paths to the end.

VALIDATES

Obstacles can create unreachable regions, and our logic correctly identifies them without explicit "connectivity checking."

Edge 4: Multiple valid detours

S  .  X  .
.  .  X  .
.  .  .  E

The obstacle forces paths to go around it. Let's trace carefully:

Row 0: [1, 1, 0, 0]  // obstacle blocks rightward propagation
Row 1: [1, 2, 0, 0]  // dp[1][1] = 1 + 1 = 2
Row 2: [1, 3, 3, 3]  // Let's calculate each:

For (2,1):

dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3

For (2,2):

dp[2][2] = dp[1][2] + dp[2][1] = 0 + 3 = 3

For (2,3):

dp[2][3] = dp[1][3] + dp[2][2] = 0 + 3 = 3

The answer is 3 paths. The obstacle eliminates some paths but allows others to flow around it.

VALIDATES

Our formula naturally handles rerouting without explicitly "finding alternate paths."

💻 Coder's Brain: Implementation Decisions

Decision 1: When to check for obstacles?

You have two options:

Option A: Check before calculating

if (grid[i][j] is obstacle) {
    dp[i][j] = 0;
} else {
    dp[i][j] = dp[i-1][j] + dp[i][j-1];
}

Option B: Calculate, then override

dp[i][j] = dp[i-1][j] + dp[i][j-1];
if (grid[i][j] is obstacle) {
    dp[i][j] = 0;
}

WHICH IS BETTER?

Option A is more efficient (avoids unnecessary addition), but both are correct.

Key insight: The obstacle check is a guard condition that prevents the normal calculation. It has priority over the recurrence relation.

Decision 2: Initialization becomes trickier

In Unique Paths I, the first row and column were simple:

First row: all 1s (keep going right)
First column: all 1s (keep going down)

But with obstacles:

S  .  X  .

If there's an obstacle at position (0,2), what happens to position (0,3)?

You can't reach it because you can't pass through the obstacle.

NEW RULE FOR INITIALIZATION

First row: Keep setting to 1 UNTIL you hit an obstacle, then all remaining cells are 0

First column: Same logic going downward

# First row
dp[0][0] = 1 if no obstacle else 0

for j in range(1, n):
    if obstacle at (0,j):
        dp[0][j] = 0
        # all subsequent cells in row 0 are also 0
    else:
        dp[0][j] = dp[0][j-1]  # inherit from left

WHY THIS WORKS

If the cell to your left is 0 (blocked), you can't reach the current cell either, so it becomes 0.

This creates a "cascade" of zeros.

Full Implementation:

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;

    if (obstacleGrid[0][0] == 1) return 0;

    int[][] dp = new int[m][n];
    dp[0][0] = 1;

    // First column
    for (int i = 1; i < m; i++) {
        dp[i][0] = (obstacleGrid[i][0] == 0 && dp[i-1][0] == 1) ? 1 : 0;
    }

    // First row
    for (int j = 1; j < n; j++) {
        dp[0][j] = (obstacleGrid[0][j] == 0 && dp[0][j-1] == 1) ? 1 : 0;
    }

    // Fill the grid
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }

    return dp[m-1][n-1];
}

Decision 3: Can we still use 1D array optimization?

Yes! The obstacle logic doesn't change the dependency structure. You still only need the previous row.

When processing cell j:

dp[j] currently holds the value from the row above (i-1, j)
dp[j-1] holds the value from the left (i, j-1)

If there's an obstacle at (i,j), you just set dp[j] = 0, overriding whatever was there.

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;

    if (obstacleGrid[0][0] == 1) return 0;

    int[] dp = new int[n];
    dp[0] = 1;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[j] = 0;
            } else if (j > 0) {
                dp[j] = dp[j] + dp[j-1];
                //      ↑       ↑
                //   from above  from left
            }
        }
    }

    return dp[n-1];
}

🔄 Comparing the Two Problems

┌─────────────────────────────────────────────────────┐
│  WHAT STAYED THE SAME                               │
└─────────────────────────────────────────────────────┘

✅ The recurrence relation:
   dp[i][j] = dp[i-1][j] + dp[i][j-1]

✅ The dependency structure:
   You need values from above and left

✅ The fundamental counting principle:
   Partition paths by their final move

┌─────────────────────────────────────────────────────┐
│  WHAT CHANGED                                       │
└─────────────────────────────────────────────────────┘

🔄 Initialization:
   First row and column can have zeros mid-way

🔄 Guard condition:
   Check for obstacles before applying recurrence

🔄 The "meaning" of 0:
   In Unique Paths I: 0 never appears (always ≥1 path)
   In Unique Paths II: 0 means "unreachable"

🎓 The Meta-Lesson

How to Adapt a Solution When Constraints Change

SYSTEMATIC ADAPTATION PROCESS

When a problem adds complexity (like obstacles), don't throw away your previous solution. Instead:

Step 1: Identify what property the new constraint violates

Obstacles violate "all cells are reachable"

Step 2: Ask if your core logic still applies in the non-violating cases

The recurrence still works for non-obstacle cells

Step 3: Find the minimal modification to handle violations

Set obstacle cells to 0

Step 4: Verify the modification propagates correctly

0 acts as identity for impossibility

BUILDING ADAPTABLE THINKING

This is how you build adaptable thinking rather than memorizing separate solutions.

🧪 Test Your Understanding

VERIFY YOUR COMPREHENSION

Question 1: If obstacles form an L-shape blocking the bottom-right corner, what would the final answer be?

Hint: The end cell itself would be blocked.

Click for answer

If the end cell (m-1, n-1) has an obstacle, then dp[m-1][n-1] = 0.

Answer: 0 paths (destination is unreachable)

This shows that our logic correctly handles destination blocking without special cases.

Question 2: Could there ever be a case where the obstacle cell itself has a non-zero value? Why or why not?

Hint: Think about what the value represents.

Click for answer

No, never.

The value dp[i][j] represents "number of ways to REACH this cell."

If the cell is an obstacle, you cannot step on it, so there are 0 ways to reach it.

Setting it to any other value would violate the meaning of our state definition.

Question 3: What happens if we process the grid in reverse order (bottom-right to top-left)? Does the obstacle logic still work?

Hint: Think about dependency direction.

Click for answer

Yes, it still works!

You'd change the recurrence to:

dp[i][j] = dp[i+1][j] + dp[i][j+1]

Obstacles would still be set to 0, and the zero-propagation logic would work the same way.

However: You'd need to initialize the last row and last column instead of the first ones.

This is what Dungeon Game does!

Question 4: Why is it incorrect to just "skip" obstacle cells during iteration rather than explicitly setting them to 0?

Hint: What would happen to cells that depend on the skipped cell?

Click for answer

If you skip without setting to 0:

// WRONG APPROACH
for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        if (obstacleGrid[i][j] == 1) continue;  // Skip!
        dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
}

Problem: The dp[i][j] array might have garbage values or old values at obstacle positions.

When a future cell calculates dp[i][j] = dp[i-1][j] + dp[i][j-1], if dp[i-1][j] is an obstacle but wasn't set to 0, it will use the wrong value!

Correct approach: Explicitly set to 0 to ensure proper propagation:

if (obstacleGrid[i][j] == 1) {
    dp[i][j] = 0;  // Must explicitly set!
}

🎯 Key Takeaways

WHAT YOU SHOULD REMEMBER

The Core Logic Survives:
- The recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1] doesn't change
- Only the guard condition changes
Zero as Identity for Impossibility:
- Setting obstacle cells to 0 automatically propagates through the grid
- No need for explicit path-checking
Initialization Complexity:
- First row/column can have cascading zeros
- One obstacle blocks everything beyond it in that row/column
The Adaptation Pattern:
- Don't reinvent from scratch
- Find the minimal modification to handle new constraints
- Verify the modification propagates correctly
Space Optimization Still Works:
- 1D array optimization is still valid
- Obstacles don't change dependency structure

🚀 Next Challenge

After mastering obstacles, try:

Minimum Path Sum - Change from counting to optimization (minimize cost)
Unique Paths III - Add "must visit all cells" constraint
Dungeon Game - Reverse direction with health constraints

Each builds on the same foundation with progressively more complex constraints.

Remember: When a problem adds constraints, your first instinct should be: "Can I adapt my existing solution?" not "Do I need a completely new approach?" Most of the time, a small modification is all you need.

🧠 Designer's Brain: The "Oh No" Moment​

Your First Reaction When Seeing Obstacles​

🤔 The Fundamental Question​

What Actually Changes When We Add Obstacles?​

🔬 Discovery Process: Building Intuition​

Experiment 1: What happens to an obstacle cell?​

Experiment 2: What happens to cells AFTER an obstacle?​

💡 The Critical Insight (What Makes This "Obvious")​

Why does setting obstacle cells to 0 automatically handle everything?​

Think About It Algebraically​

🎯 Deeper Understanding: Why Addition Still Works​

The Partition Principle Revisited​

🚨 Edge Cases as Concept Validators​

Edge 1: Start position has obstacle​

Edge 2: End position has obstacle​

Edge 3: Obstacle creates an impossible barrier​

Edge 4: Multiple valid detours​

💻 Coder's Brain: Implementation Decisions​

Decision 1: When to check for obstacles?​

Decision 2: Initialization becomes trickier​

Decision 3: Can we still use 1D array optimization?​

🔄 Comparing the Two Problems​

🎓 The Meta-Lesson​

How to Adapt a Solution When Constraints Change​

🧪 Test Your Understanding​

🎯 Key Takeaways​

🚀 Next Challenge​

🧠 Designer's Brain: The "Oh No" Moment

Your First Reaction When Seeing Obstacles

🤔 The Fundamental Question

What Actually Changes When We Add Obstacles?

🔬 Discovery Process: Building Intuition

Experiment 1: What happens to an obstacle cell?

Experiment 2: What happens to cells AFTER an obstacle?

💡 The Critical Insight (What Makes This "Obvious")

Why does setting obstacle cells to 0 automatically handle everything?

Think About It Algebraically

🎯 Deeper Understanding: Why Addition Still Works

The Partition Principle Revisited

🚨 Edge Cases as Concept Validators

Edge 1: Start position has obstacle

Edge 2: End position has obstacle

Edge 3: Obstacle creates an impossible barrier

Edge 4: Multiple valid detours

💻 Coder's Brain: Implementation Decisions

Decision 1: When to check for obstacles?

Decision 2: Initialization becomes trickier

Decision 3: Can we still use 1D array optimization?

🔄 Comparing the Two Problems

🎓 The Meta-Lesson

How to Adapt a Solution When Constraints Change

🧪 Test Your Understanding

🎯 Key Takeaways

🚀 Next Challenge