🧩 Unique Paths II - The Discovery Journey
How to adapt your solution when constraints change: The obstacle challenge
📘 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 (Quick Glance)
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: A 3×3 grid with center cell blocked:
S . .
. X .
. . E
→ Answer: 2 unique paths (instead of 6)
Initial Observations:
- Everything from Unique Paths I applies, EXCEPT some cells are blocked
- Blocked cells cannot be stepped on
- Need to figure out how obstacles affect path counting
Let's start solving!
1. My First Approach: Thinking Recursively
My thought process:
"I know how to solve Unique Paths I recursively:
- To reach (i,j), I came from (i-1,j) or (i,j-1)
- Count paths from both sources
With obstacles... what changes?"
The Critical Question: Can I still use the same recursive structure?
Solution 1: Unoptimized Recursive (Brute Force)
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
// Edge case: start or end is blocked
if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
return 0;
}
return countPaths(obstacleGrid, 0, 0, m, n);
}
private int countPaths(int[][] grid, int i, int j, int m, int n) {
// Base case: reached destination
if (i == m - 1 && j == n - 1) {
return 1;
}
// Out of bounds
if (i >= m || j >= n) {
return 0;
}
// Hit an obstacle
if (grid[i][j] == 1) {
return 0;
}
// Choice 1: Move right
int pathsRight = countPaths(grid, i, j + 1, m, n);
// Choice 2: Move down
int pathsDown = countPaths(grid, i + 1, j, m, n);
// Total paths = sum of both choices
return pathsRight + pathsDown;
}
}
Complexity Analysis:
- Time: O(2^(m+n)) - Exponential! Each cell branches into 2 recursive calls
- Space: O(m+n) - Recursion call stack depth
Why This Is Slow:
countPaths(0,0)
├── countPaths(0,1)
│ ├── countPaths(0,2) ← Calculated here
│ │ └── ...
│ └── countPaths(1,2)
│ └── ...
└── countPaths(1,0)
├── countPaths(1,1)
│ ├── countPaths(1,2) ← Calculated AGAIN here!
│ └── countPaths(2,1)
└── countPaths(2,0)
└── ...
I'm recalculating the same cells over and over!
countPaths(1,2) gets computed multiple times from different paths.
My realization: "The recursive logic works! Obstacles just return 0 paths. But I'm repeating work..."
Execution Trace for 3×3 grid with center obstacle:
Grid:
S . .
. X .
. . E
countPaths(0,0): Not obstacle ✓
├─ Move right → countPaths(0,1)
│ ├─ Move right → countPaths(0,2)
│ │ ├─ Move right → out of bounds → 0
│ │ └─ Move down → countPaths(1,2)
│ │ ├─ Move right → out of bounds → 0
│ │ └─ Move down → countPaths(2,2) → 1
│ │ Returns: 1
│ └─ Move down → countPaths(1,1)
│ Hit obstacle! → 0
│ Returns: 1
└─ Move down → countPaths(1,0)
├─ Move right → countPaths(1,1)
│ Hit obstacle! → 0
└─ Move down → countPaths(2,0)
├─ Move right → countPaths(2,1)
│ ├─ Move right → countPaths(2,2) → 1
│ └─ Move down → out of bounds → 0
│ Returns: 1
└─ Move down → out of bounds → 0
Returns: 1
Returns: 1
Total: 1 + 1 = 2 ✓
2. Optimization Round 1: Adding Memoization (Top-Down DP)
My thought: "Let me cache the results so I don't recalculate them!"
Solution 2: Top-Down DP with Memoization
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
// Edge case: start or end is blocked
if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
return 0;
}
// Memo: memo[i][j] = number of paths from (i,j) to end
// Use Integer to distinguish "not computed" (null) from "computed as 0"
Integer[][] memo = new Integer[m][n];
return countPaths(obstacleGrid, 0, 0, m, n, memo);
}
private int countPaths(int[][] grid, int i, int j, int m, int n, Integer[][] memo) {
// Base case: reached destination
if (i == m - 1 && j == n - 1) {
return 1;
}
// Out of bounds
if (i >= m || j >= n) {
return 0;
}
// Hit an obstacle
if (grid[i][j] == 1) {
return 0;
}
// ✨ MEMOIZATION CHECK: Have we solved this cell before?
if (memo[i][j] != null) {
return memo[i][j]; // Cache hit! 🚀
}
// Choice 1: Move right
int pathsRight = countPaths(grid, i, j + 1, m, n, memo);
// Choice 2: Move down
int pathsDown = countPaths(grid, i + 1, j, m, n, memo);
// ✨ CACHE THE RESULT before returning
memo[i][j] = pathsRight + pathsDown;
return memo[i][j];
}
}
Complexity Analysis:
- Time: O(m×n) - Each cell computed once! ✨
- Space: O(m×n) memo array + O(m+n) call stack
Only 3 additions to the pure recursive solution!
- Create memo array
- Check cache before computing
- Store result in cache before returning
Why This Is Fast:
countPaths(0,0, memo) [memo = all nulls]
├─ countPaths(0,1, memo)
│ ├─ countPaths(0,2, memo) → computed and cached
│ └─ countPaths(1,1, memo) → obstacle → 0
│ Result: memo[0][1] = 1
└─ countPaths(1,0, memo)
├─ countPaths(1,1, memo) → obstacle → 0
└─ countPaths(2,0, memo)
├─ countPaths(2,1, memo) → computed and cached
└─ ...
Result: memo[1][0] = 1
Total: 1 + 1 = 2
Final memo: Each cell computed exactly once!
Each cell is computed exactly once and reused from cache.
Time complexity drops from O(2^(m+n)) to O(m×n)! 🎉
My next thought: "This is much better! But I'm still using recursion. Can I build it iteratively?"
3. Optimization Round 2: Going Iterative (Bottom-Up DP)
My thought: "Instead of recursing from start to end, what if I build the solution cell by cell?"
Solution 3: Bottom-Up DP with Tabulation
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
// Edge case: start is blocked
if (obstacleGrid[0][0] == 1) {
return 0;
}
// dp[i][j] = number of ways to reach cell (i,j) from start
int[][] dp = new int[m][n];
// BASE CASE: Start position
dp[0][0] = 1;
// INITIALIZE FIRST COLUMN
// Can only move down, so paths = 1 UNTIL we hit obstacle
for (int i = 1; i < m; i++) {
if (obstacleGrid[i][0] == 1) {
dp[i][0] = 0; // Obstacle blocks
// All cells below are also unreachable
} else {
dp[i][0] = dp[i-1][0]; // Inherit from above
}
}
// INITIALIZE FIRST ROW
// Can only move right, so paths = 1 UNTIL we hit obstacle
for (int j = 1; j < n; j++) {
if (obstacleGrid[0][j] == 1) {
dp[0][j] = 0; // Obstacle blocks
// All cells to the right are also unreachable
} else {
dp[0][j] = dp[0][j-1]; // Inherit from left
}
}
// FILL THE GRID
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
// Obstacle: no paths through here
dp[i][j] = 0;
} else {
// Normal cell: sum paths from above and left
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
}
Complexity Analysis:
- Time: O(m×n) - Visit each cell once
- Space: O(m×n) - DP array only (no recursion stack!)
Why Bottom-Up?
- ✅ No recursion overhead - Simple loops instead of function calls
- ✅ No stack overflow risk - Works for very large grids
- ✅ Better cache locality - Sequential memory access
- ✅ Easier to optimize further - Can reduce to O(n) space
Execution Trace for 3×3 grid with center obstacle:
Grid:
0 0 0
0 1 0
0 0 0
Initial: dp[0][0] = 1
First column:
dp[1][0] = dp[0][0] = 1 (no obstacle)
dp[2][0] = dp[1][0] = 1 (no obstacle)
First row:
dp[0][1] = dp[0][0] = 1 (no obstacle)
dp[0][2] = dp[0][1] = 1 (no obstacle)
After initialization:
1 1 1
1 ? ?
1 ? ?
Fill grid (i=1, j=1):
obstacleGrid[1][1] == 1 → dp[1][1] = 0
Fill grid (i=1, j=2):
dp[1][2] = dp[0][2] + dp[1][1] = 1 + 0 = 1
Fill grid (i=2, j=1):
dp[2][1] = dp[1][1] + dp[2][0] = 0 + 1 = 1
Fill grid (i=2, j=2):
dp[2][2] = dp[1][2] + dp[2][1] = 1 + 1 = 2
Final DP table:
1 1 1
1 0 1
1 1 2
Return: dp[2][2] = 2 ✓
dp[i][j] = dp[i-1][j] + dp[i][j-1]
This formula doesn't change from Unique Paths I!
Only the guard condition (checking for obstacles) is added.
My observation: "The 2D array is nice, but I only need the previous row. Can I optimize space?"
4. Final Optimization: Space Optimization (O(n) Space)
My thought: "Since I only look at the previous row and current row, I can use just one 1D array!"
Solution 4: Space-Optimized Bottom-Up
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
// Edge case: start is blocked
if (obstacleGrid[0][0] == 1) {
return 0;
}
// Use 1D array: dp[j] = number of ways to reach current cell at column j
int[] dp = new int[n];
dp[0] = 1; // Starting position
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
// Obstacle: set to 0
dp[j] = 0;
} else if (j > 0) {
// Normal cell: add paths from left
dp[j] = dp[j] + dp[j-1];
// ↑ ↑
// from above from left
}
// Note: when j==0, dp[j] already holds the value from above
}
}
return dp[n-1];
}
}
Complexity Analysis:
- Time: O(m×n) - Same as before
- Space: O(n) - Only one 1D array! 🎯
Execution Trace for 3×3 grid with center obstacle:
Grid:
0 0 0
0 1 0
0 0 0
Initial: dp = [1, 0, 0]
Row 0 (i=0):
j=0: obstacleGrid[0][0]=0, j==0 → dp[0] stays 1
j=1: obstacleGrid[0][1]=0, j>0 → dp[1] = dp[1] + dp[0] = 0 + 1 = 1
j=2: obstacleGrid[0][2]=0, j>0 → dp[2] = dp[2] + dp[1] = 0 + 1 = 1
dp = [1, 1, 1]
Row 1 (i=1):
j=0: obstacleGrid[1][0]=0, j==0 → dp[0] stays 1
j=1: obstacleGrid[1][1]=1 → dp[1] = 0 (obstacle!)
j=2: obstacleGrid[1][2]=0, j>0 → dp[2] = dp[2] + dp[1] = 1 + 0 = 1
dp = [1, 0, 1]
Row 2 (i=2):
j=0: obstacleGrid[2][0]=0, j==0 → dp[0] stays 1
j=1: obstacleGrid[2][1]=0, j>0 → dp[1] = dp[1] + dp[0] = 0 + 1 = 1
j=2: obstacleGrid[2][2]=0, j>0 → dp[2] = dp[2] + dp[1] = 1 + 1 = 2
dp = [1, 1, 2]
Return: dp[2] = 2 ✓
At each cell (i,j):
- dp[j] currently holds value from cell (i-1,j) (from above)
- dp[j-1] holds value from cell (i,j-1) (from left)
When we update dp[j] = dp[j] + dp[j-1], we're implementing:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
The obstacle logic doesn't change this - we just set dp[j] = 0 when needed!
5. Solution Evolution Summary
| Approach | Time | Space | Recursion? | Key Insight |
|---|---|---|---|---|
| 1. Unoptimized Recursive | O(2^(m+n)) | O(m+n) stack | Yes | Obstacles just return 0 |
| 2. Top-Down (Memoization) | O(m×n) | O(m×n) + O(m+n) stack | Yes | Cache eliminates redundant work |
| 3. Bottom-Up (Tabulation) | O(m×n) | O(m×n) array | No | Build iteratively from start |
| 4. Space-Optimized | O(m×n) | O(n) | No | Only need current and previous row |
The Learning Journey:
- 🤔 Start with natural recursive thinking - obstacles = 0 paths
- 💡 Realize we're repeating work → add memoization
- ⚡ Eliminate recursion overhead → go bottom-up
- 🎯 Recognize we only need previous row → space optimize
6. Deep Dive: Understanding Why This Works
Now that we've built the solution, let's understand the deeper concepts.
6.1 The Power of Zero
Why Setting Obstacles to 0 Works
When you set an obstacle cell to 0, you're encoding something powerful:
"This cell contributes NOTHING to any downstream calculations."
Think About It Algebraically:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
If one source is an obstacle (value 0):
dp[i][j] = dp[i-1][j] + 0 // or
dp[i][j] = 0 + dp[i][j-1]
Zero acts as an identity element for impossibility:
"Ignore this direction; it contributes no paths."
The beautiful part: This propagates automatically through your entire grid without special logic!
6.2 Initialization with Obstacles
First Row and Column Complexity
In Unique Paths I, initialization was simple:
- First row: all 1s (keep going right)
- First column: all 1s (keep going down)
With obstacles:
S . X .
If there's an obstacle at position (0,2), position (0,3) is unreachable!
First row: Keep setting to 1 UNTIL you hit an obstacle, then all remaining cells are 0
First column: Same logic going downward
Implementation:
// First column
for (int i = 1; i < m; i++) {
if (obstacleGrid[i][0] == 1) {
dp[i][0] = 0;
} else {
dp[i][0] = dp[i-1][0]; // Inherit from above
}
}
// First row
for (int j = 1; j < n; j++) {
if (obstacleGrid[0][j] == 1) {
dp[0][j] = 0;
} else {
dp[0][j] = dp[0][j-1]; // Inherit from left
}
}
If the cell to your left/above is 0 (blocked), you can't reach the current cell either, so it becomes 0.
This creates a "cascade" of zeros.
6.3 The Guard Condition Pattern
The obstacle check is a guard condition that has priority over the normal recurrence:
if (obstacleGrid[i][j] == 1) {
// Guard condition: override everything
dp[i][j] = 0;
} else {
// Normal case: apply recurrence
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
This pattern appears in many DP problems where certain states are invalid or special.
7. Edge Cases & Validation
7.1 Critical Edge Cases
Edge Case 1: Start Position Has Obstacle
X . .
. . .
. . E
If you can't even start, how many paths exist? Zero.
Does our logic handle this?
- Yes: We check
obstacleGrid[0][0] == 1at the beginning and return 0 immediately.
Edge Case 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
dp[m-1][n-1], where we set it to 0 if there's an obstacle.
Edge Case 3: Obstacle Creates 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.
Obstacles create unreachable regions, and our logic correctly identifies them without explicit "connectivity checking."
Edge Case 4: Multiple Valid Detours
S . X .
. . X .
. . . E
The obstacle forces paths to go around it. Let's trace:
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] // paths flow around the obstacle
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. Natural rerouting!
8. Mastery & Key Takeaways
8.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"
8.2 The Adaptation Pattern
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
8.3 Key Takeaways
- ✅ Start with recursion: Obstacles naturally return 0 paths
- ✅ Optimize with memoization: Eliminate redundant computation (O(2^(m+n)) → O(m×n))
- ✅ Convert to bottom-up: Remove recursion overhead
- ✅ Space optimize: Only need previous row (O(m×n) → O(n))
- ✅ The core recurrence doesn't change: Only guard conditions added
- ✅ Zero propagation is automatic: Math handles it, no special routing logic needed
- ✅ Initialization requires care: First row/column can have cascading zeros
- ✅ Guard conditions override recurrence: Pattern appears in many DP problems
The Learning Journey: Adapt existing solutions rather than reinventing from scratch!
- Start with recursion - Show you can adapt Unique Paths I
- Add memoization - Demonstrate optimization awareness
- Convert to bottom-up - Show you can eliminate recursion
- Optimize space - Prove you understand dependency patterns
Each step builds on the previous! 🎓
The Evolution Path:
Pure Recursion (O(2^(m+n)) time)
↓ "Same cells computed multiple times"
Top-Down with Memo (O(m×n) time, O(m×n) space)
↓ "Still using recursion - can we eliminate?"
Bottom-Up DP (O(m×n) time, O(m×n) space)
↓ "Do we really need the entire grid?"
Space-Optimized (O(m×n) time, O(n) space) ✨
From Unique Paths I to Unique Paths II by adding ONE guard condition.
This teaches you how to adapt solutions when constraints change - a critical skill for hundreds of problems! 🎯