Unique Paths II

Medium

💭 Introduction

You’re given an m x n grid where a robot starts at the top-left corner and wants to reach the bottom-right corner. The robot can only move right or down at any point in time.

But here’s the twist: some cells contain obstacles that the robot cannot pass through!

Your task is to find the number of unique paths the robot can take to reach the destination while avoiding obstacles.

🧩 Problem Statement

LeetCode #63 — Unique Paths II

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

🔍 Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2

Explanation:

Start → [0,0,0]
        [0,X,0]  (X = obstacle)
   End → [0,0,0]

There are 2 ways to reach the bottom-right corner:

Right → Right → Down → Down
Down → Down → Right → Right

🔍 Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Explanation:

Start → [0,X]
   End → [0,0]

There is only 1 way: Down → Right

🔍 Example 3:

Input: obstacleGrid = [[1]]
Output: 0

Explanation:

The starting position itself has an obstacle, so there are 0 paths.

🧠 Step 1: Understanding the Problem

Let’s break down the key points:

Movement Rules:

Can only move right or down
Cannot move through obstacles (cells with value 1)
Must reach from top-left to bottom-right

Key Observations:

If starting position has an obstacle → return 0
If ending position has an obstacle → return 0
For any cell, paths = paths from above + paths from left (if no obstacle)
If a cell has an obstacle → paths through it = 0

Relation to Unique Paths I: This is an extension of the classic Unique Paths problem, but with obstacles that block certain paths.

🤔 Step 2: The Recursive Approach

Let’s think recursively:

paths(i, j) = 0                                    if grid[i][j] == 1 (obstacle)
            = 1                                    if i == 0 and j == 0 (start)
            = paths(i-1, j) + paths(i, j-1)       otherwise

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    
    def helper(i, j):
        # Out of bounds
        if i < 0 or j < 0:
            return 0
        
        # Obstacle
        if obstacleGrid[i][j] == 1:
            return 0
        
        # Starting position
        if i == 0 and j == 0:
            return 1
        
        # Sum paths from top and left
        return helper(i - 1, j) + helper(i, j - 1)
    
    return helper(m - 1, n - 1)

Problem: This has exponential time complexity due to overlapping subproblems!

⏱️ Time Complexity: $O(2^{m+n})$

📦 Space Complexity: $O(m + n)$ for recursion stack

🚀 Step 3: Top-Down DP (Memoization)

We can cache results to avoid recomputation:

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        
        # Edge case: start or end has obstacle
        if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1:
            return 0
        
        memo = {}
        
        def dp(i, j):
            # Out of bounds
            if i < 0 or j < 0:
                return 0
            
            # Obstacle
            if obstacleGrid[i][j] == 1:
                return 0
            
            # Starting position
            if i == 0 and j == 0:
                return 1
            
            # Check memo
            if (i, j) in memo:
                return memo[(i, j)]
            
            # Calculate paths
            memo[(i, j)] = dp(i - 1, j) + dp(i, j - 1)
            return memo[(i, j)]
        
        return dp(m - 1, n - 1)

⏱️ Time Complexity: $O(m \times n)$

📦 Space Complexity: $O(m \times n)$ for memoization

⚙️ Step 4: Bottom-Up DP (Tabulation)

Let’s build a table from the ground up:

Define: dp[i][j] = number of unique paths to reach cell (i, j)

Recurrence relation:

dp[i][j] = 0                           if obstacleGrid[i][j] == 1
         = dp[i-1][j] + dp[i][j-1]     otherwise

Base case:

dp[0][0] = 1 if obstacleGrid[0][0] == 0, else 0

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        
        # Edge case: start or end has obstacle
        if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1:
            return 0
        
        # Create DP table
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1
        
        # Fill first row
        for j in range(1, n):
            if obstacleGrid[0][j] == 0:
                dp[0][j] = dp[0][j-1]
            else:
                dp[0][j] = 0
        
        # Fill first column
        for i in range(1, m):
            if obstacleGrid[i][0] == 0:
                dp[i][0] = dp[i-1][0]
            else:
                dp[i][0] = 0
        
        # Fill rest of the table
        for i in range(1, m):
            for j in range(1, n):
                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]

Let’s trace through Example 1: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

i\j	0	1	2
0	1	1	1
1	1	0	1
2	1	1	2

Step-by-step:

dp[0][0] = 1 (start)
dp[0][1] = 1 (from left)
dp[0][2] = 1 (from left)
dp[1][0] = 1 (from above)
dp[1][1] = 0 (obstacle!)
dp[1][2] = 1 (only from above, since left is obstacle)
dp[2][0] = 1 (from above)
dp[2][1] = 1 (from above, since left is 1)
dp[2][2] = 2 (from above: 1, from left: 1)

Final answer: 2 ✓

⏱️ Time Complexity: $O(m \times n)$

📦 Space Complexity: $O(m \times n)$

🧮 Step 5: Space Optimization (1D DP)

We can optimize space by using only one row:

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        
        # Edge case: start or end has obstacle
        if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1:
            return 0
        
        # Use single row
        dp = [0] * n
        dp[0] = 1
        
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[j] = 0
                elif j > 0:
                    dp[j] += dp[j-1]
        
        return dp[n-1]

How it works:

dp[j] represents paths to current cell in current row
When we process a cell, dp[j] already contains paths from above (previous iteration)
We add dp[j-1] which contains paths from left (current iteration)

⏱️ Time Complexity: $O(m \times n)$

📦 Space Complexity: $O(n)$ — Optimal!

🎯 Key Insights

Obstacle handling: Any cell with obstacle has 0 paths through it
Edge cases matter: Check if start or end has obstacle before processing
First row/column: Must be handled carefully since they only have one direction
DP state: dp[i][j] = sum of paths from top and left (if no obstacle)
Space optimization: Only need previous row’s values, so can use 1D array

📊 Complexity Summary

Approach	Time	Space	Notes
Naive Recursion	$O(2^{m+n})$	$O(m+n)$	Too slow
Memoization	$O(m \times n)$	$O(m \times n)$	Top-down DP
2D Tabulation	$O(m \times n)$	$O(m \times n)$	Bottom-up DP
1D Tabulation	$O(m \times n)$	$O(n)$	Space optimized

🌟 Edge Cases to Consider

Start has obstacle: [[1]] → Return 0
End has obstacle: [[0,0],[0,1]] → Return 0
Single cell no obstacle: [[0]] → Return 1
All obstacles: [[1,1],[1,1]] → Return 0
No obstacles: Same as Unique Paths I
Obstacle blocks all paths: [[0,1],[1,0]] → Return 0

💡 Common Mistakes

Forgetting to check start/end: Must verify no obstacle at start or end
Wrong first row/column initialization: Obstacles break the chain
Not handling obstacles in DP: Must set dp[i][j] = 0 for obstacles
Off-by-one errors: Be careful with array indices
Modifying input: Some solutions modify the grid, which may not be allowed

🧪 Step-by-Step Example

Let’s trace through obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]:

Initial Grid:
[0, 0, 0]
[0, X, 0]  (X = obstacle)
[0, 0, 0]

DP Table Construction:
Step 1: Initialize first cell
[1, 0, 0]
[0, 0, 0]
[0, 0, 0]

Step 2: Fill first row (can only come from left)
[1, 1, 1]
[0, 0, 0]
[0, 0, 0]

Step 3: Fill first column (can only come from above)
[1, 1, 1]
[1, 0, 0]
[1, 0, 0]

Step 4: Fill remaining cells
[1, 1, 1]
[1, 0, 1]  ← dp[1][2] = dp[0][2] + 0 (obstacle at left)
[1, 1, 2]  ← dp[2][2] = dp[1][2] + dp[2][1] = 1 + 1 = 2

Answer: 2 paths

🔍 Variations of This Problem

Unique Paths I — Same problem without obstacles
Minimum Path Sum — Find path with minimum sum
Unique Paths III — Visit every non-obstacle cell exactly once
Dungeon Game — Similar grid DP with health constraints

House Robber - Linear DP pattern
Maximum Subarray - 1D DP optimization
Minimum Path Sum - Similar grid DP
Triangle - Similar path counting

🏆 Why This Problem Matters

Grid DP foundation: Classic example of 2D DP
Obstacle handling: Teaches conditional DP transitions
Space optimization: Shows how to reduce from 2D to 1D
Real-world applications: Pathfinding, robotics, game development
Interview favorite: Common in coding interviews

🎓 Key Takeaways

Grid DP pattern: Build solution cell by cell, row by row
Obstacle = 0 paths: Any obstacle blocks all paths through it
Edge initialization: First row and column need special handling
Space optimization: Can reduce from O(m×n) to O(n) space
Edge cases: Always check start and end positions for obstacles

📝 Interview Tips

Clarify constraints: Ask about grid size, obstacle representation
Check edge cases: Start with obstacles at start/end positions
Explain approach: Start with 2D DP, then mention space optimization
Trace example: Walk through a small example to verify logic
Discuss complexity: Explain both time and space complexity

Unique Paths II

💭 Introduction

🔍 Example 1:

🔍 Example 2:

🔍 Example 3:

🧠 Step 1: Understanding the Problem

🤔 Step 2: The Recursive Approach

🚀 Step 3: Top-Down DP (Memoization)

⚙️ Step 4: Bottom-Up DP (Tabulation)

🧮 Step 5: Space Optimization (1D DP)

🎯 Key Insights

📊 Complexity Summary

🌟 Edge Cases to Consider

💡 Common Mistakes

🧪 Step-by-Step Example

🔍 Variations of This Problem

💡 Related Problems

🏆 Why This Problem Matters

🎓 Key Takeaways

📝 Interview Tips