Unique Paths II

• Difficulty: Medium
• Topics: Array, Dynamic Programming, Matrix
• Link: https://leetcode.com/problems/unique-paths-ii/

Problem Description

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.

The testcases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

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

Constraints:

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1.

Solution

Unique Paths II - Comprehensive Solution

1. Problem Deconstruction (500+ words)

Rewriting the Problem

Technical Version

Given an $m \times n$ binary matrix obstacleGrid where:

• obstacleGrid[i][j] = 0 represents a traversable cell
• obstacleGrid[i][j] = 1 represents an obstacle cell
• The robot starts at position $(0,0)$ (top-left)
• The robot must reach position $(m-1, n-1)$ (bottom-right)
• The robot can only move down ($i \rightarrow i+1$) or right ($j \rightarrow j+1$)
• A valid path is any sequence of moves from $(0,0)$ to $(m-1, n-1)$ that:
  1. Stays within grid boundaries $0 \leq i < m$, $0 \leq j < n$
  2. Never visits any cell $(i,j)$ where obstacleGrid[i][j] = 1

Compute the cardinality of the set of all valid paths: $|\mathcal{P}|$ where:

$$\mathcal{P} = \{ \text{sequences } (i_0,j_0),(i_1,j_1),\dots,(i_k,j_k) \mid (i_0,j_0)=(0,0), (i_k,j_k)=(m-1,n-1), \\ \forall t: (i_{t+1}=i_t+1 \land j_{t+1}=j_t) \lor (i_{t+1}=i_t \land j_{t+1}=j_t+1), \\ \forall t: \text{obstacleGrid}[i_t][j_t] = 0 \}$$

Beginner Version

Imagine a city laid out in a perfect grid of streets. Some intersections are blocked by construction (obstacles). You need to walk from the northwest corner to the southeast corner, but you can only walk south (down) or east (right). How many different routes can you take without passing through any blocked intersections?

Mathematical Formulation

Let $f(i,j)$ be the number of ways to reach cell $(i,j)$ from $(0,0)$. The recurrence relation is:

$$f(i,j) = \begin{cases} 0 & \text{if } \text{grid}[i][j] = 1 \ (\text{obstacle}) \\ 1 & \text{if } i=0, j=0 \text{ and no obstacle} \\ f(i-1,j) + f(i,j-1) & \text{otherwise} \end{cases}$$

With boundary conditions:

• $f(i,j) = 0$ when $i<0$ or $j<0$ (out of bounds)
• For first row ($i=0$): $f(0,j) = f(0,j-1)$ (only from left)
• For first column ($j=0$): $f(i,0) = f(i-1,0)$ (only from above)

The solution is $f(m-1, n-1)$.

Constraint Analysis

Constraint	Implication	Hidden Edge Cases
1 <= m, n <= 100	Grid size is moderate. Brute force $O(2^{m+n})$ is impossible ($2^{200} \approx 1.6 \times 10^{60}$). Need polynomial solution.	Maximum grid size is $100 \times 100 = 10^4$ cells. DP with $O(mn)$ time ($10^4$ operations) and $O(mn)$ space ($10^4$ entries) is feasible.
obstacleGrid[i][j] ∈ {0,1}	Binary values simplify logic. No need for complex comparison.	Zero values must be handled: 0 means empty, 1 means obstacle. Edge case: start/end cells could be obstacles.
Answer ≤ $2 \times 10^9$	Can use 32-bit integers (int in most languages). No need for big integers.	Count could be 0 (if blocked) or up to $\binom{m+n-2}{m-1}$ without obstacles. For $m=n=100$, maximum is $\binom{198}{99} \approx 9 \times 10^{58}$, but constraints ensure answer ≤ $2 \times 10^9$.
Hidden: Grid can be tall or wide	Algorithm should work for any aspect ratio (1×100 or 100×1).	Single row/column cases need special handling. If only one cell exists (1×1), answer is 1 if no obstacle, 0 otherwise.

Additional Edge Cases:

1. Start cell is obstacle: Immediately return 0 (no paths possible).
2. End cell is obstacle: All paths blocked, return 0.
3. Single isolated path: A corridor with obstacles on both sides.
4. Completely blocked: A row or column of obstacles cutting off all paths.
5. Large open grid: No obstacles, reduces to combinatorial problem $\binom{m+n-2}{m-1}$.

2. Intuition Scaffolding

Three Analogies

Real-World Metaphor: City Navigation

Imagine Manhattan’s grid system with some streets closed for construction. You need to go from the Upper West Side (northwest) to the Financial District (southeast), only moving south or east. Each closed street intersection eliminates all routes that would pass through it. The number of possible routes diminishes exponentially with each obstacle, especially near critical choke points.

Gaming Analogy: Tactical Movement in Strategy Games

In games like chess or tactical RPGs, a unit can only move downward or rightward (like a pawn with limited moves). Some squares contain traps (obstacles). You need to calculate how many safe movement sequences exist from your starting position to the target. Each trap square becomes a “dead end” for all paths passing through it, creating a dynamic where you must plan around danger zones.

Mathematical Analogy: Lattice Path Counting with Forbidden Points

This is a classic problem in combinatorics: counting monotonic lattice paths from $(0,0)$ to $(m,n)$ that avoid certain forbidden lattice points. Without obstacles, the count is given by binomial coefficients: $\binom{m+n}{m}$. With obstacles, we use the principle of inclusion-exclusion or dynamic programming to subtract paths through forbidden points.

Common Pitfalls (5+ Examples)

1. Ignoring start/end obstacles: Forgetting to check if $(0,0)$ or $(m-1,n-1)$ is blocked.
2. Incorrect DP initialization: Setting first row/column to all 1’s without considering obstacles.
3. Integer overflow: While constraints say answer ≤ $2\times10^9$, intermediate calculations in some approaches might overflow.
4. Overcounting paths through obstacles: If an obstacle makes a cell unreachable, all paths through it should be zero, not just subtracted.
5. Misunderstanding movement constraints: Thinking diagonal moves are allowed, or that you can go up/left.
6. Using BFS/DFS for counting: These explore all paths explicitly, leading to exponential time.
7. Trying combinatorial formula with obstacles: The binomial coefficient formula doesn’t easily generalize to arbitrary obstacle configurations.

3. Approach Encyclopedia

Approach 1: Brute Force Recursion

Concept: Explore all possible paths via recursion, counting only those that reach the destination without hitting obstacles.

Pseudocode:

def count_paths(i, j, grid):
    m, n = len(grid), len(grid[0])
    
    # Base case: out of bounds or obstacle
    if i >= m or j >= n or grid[i][j] == 1:
        return 0
    
    # Base case: reached destination
    if i == m-1 and j == n-1:
        return 1
    
    # Recursive case: try moving down and right
    down_paths = count_paths(i+1, j, grid)
    right_paths = count_paths(i, j+1, grid)
    
    return down_paths + right_paths

# Initial call: count_paths(0, 0, obstacleGrid)

Complexity Proof:

• Time: Each call makes 2 recursive calls, creating a binary tree of depth $m+n-2$. Total nodes ≈ $2^{m+n-2} = O(2^{m+n})$.
• Space: Recursion stack depth = $m+n-2 = O(m+n)$.

Visualization:

Start (0,0)
├── Move Down → (1,0)
│   ├── Down → (2,0) ...
│   └── Right → (1,1) ...
└── Move Right → (0,1)
    ├── Down → (1,1) ...
    └── Right → (0,2) ...

Obstacle at (1,1) would prune:
  (0,0)→(0,1)→(1,1) ✗
  (0,0)→(1,0)→(1,1) ✗

Approach 2: Memoized Recursion (Top-Down DP)

Concept: Cache results of subproblems to avoid recomputation.

Pseudocode:

def uniquePathsWithObstacles(grid):
    m, n = len(grid), len(grid[0])
    memo = [[-1] * n for _ in range(m)]
    
    def dfs(i, j):
        # Check bounds and obstacles
        if i >= m or j >= n or grid[i][j] == 1:
            return 0
        
        # Check if reached destination
        if i == m-1 and j == n-1:
            return 1
        
        # Return cached result if available
        if memo[i][j] != -1:
            return memo[i][j]
        
        # Compute and cache
        memo[i][j] = dfs(i+1, j) + dfs(i, j+1)
        return memo[i][j]
    
    return dfs(0, 0)

Complexity Proof:

• Time: $O(mn)$ - each cell computed once.
• Space: $O(mn)$ for memoization + $O(m+n)$ recursion stack.

Visualization:

Grid 3x3, obstacle at (1,1)
memo table computation order:
(0,0) → needs (1,0) and (0,1)
  (1,0) → needs (2,0) and (1,1)
    (2,0) → needs (2,1) ...
    (1,1) → obstacle → 0
  (0,1) → needs (1,1) and (0,2)
    (1,1) → 0 (cached)
    (0,2) → ...

Approach 3: Bottom-Up Dynamic Programming (2D Table)

Concept: Build solution from base cases to final answer using a 2D DP table.

Pseudocode:

def uniquePathsWithObstacles(grid):
    m, n = len(grid), len(grid[0])
    
    # If start or end is blocked
    if grid[0][0] == 1 or grid[m-1][n-1] == 1:
        return 0
    
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1  # One way to be at start
    
    # Fill first column (only from above)
    for i in range(1, m):
        if grid[i][0] == 0:  # Not obstacle
            dp[i][0] = dp[i-1][0]
    
    # Fill first row (only from left)
    for j in range(1, n):
        if grid[0][j] == 0:  # Not obstacle
            dp[0][j] = dp[0][j-1]
    
    # Fill rest of the table
    for i in range(1, m):
        for j in range(1, n):
            if grid[i][j] == 0:  # Not obstacle
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            # else remains 0 (obstacle)
    
    return dp[m-1][n-1]

Complexity Proof:

• Time: $O(mn)$ - nested loops over all cells.
• Space: $O(mn)$ for DP table.

Mathematical Derivation: Let $dp[i][j]$ = number of paths to $(i,j)$. The recurrence:

$$dp[i][j] = \begin{cases} 0 & \text{if } grid[i][j] = 1 \\ dp[i-1][j] + dp[i][j-1] & \text{if } grid[i][j] = 0 \text{ and } i,j>0 \\ dp[i-1][0] & \text{if } j=0, i>0, grid[i][0]=0 \\ dp[0][j-1] & \text{if } i=0, j>0, grid[0][j]=0 \\ 1 & \text{if } i=0, j=0, grid[0][0]=0 \end{cases}$$

Approach 4: Space-Optimized DP (1D Array)

Concept: Since we only need previous row and current row, use a 1D array of size $n$.

Pseudocode:

def uniquePathsWithObstacles(grid):
    m, n = len(grid), len(grid[0])
    
    if grid[0][0] == 1 or grid[m-1][n-1] == 1:
        return 0
    
    dp = [0] * n
    dp[0] = 1  # Starting cell
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                dp[j] = 0  # Obstacle clears all paths to this cell
            elif j > 0:
                dp[j] = dp[j] + dp[j-1]
            # For j=0, dp[0] persists if not obstacle
    
    return dp[n-1]

How it works:

• dp[j] stores paths to current row’s column j
• When processing cell (i,j):
  • If obstacle: dp[j] = 0 (no paths through here)
  • Else: dp[j] = dp[j] + dp[j-1]
    • dp[j] = paths from above (previous row, same column)
    • dp[j-1] = paths from left (current row, previous column)

Complexity Proof:

• Time: $O(mn)$
• Space: $O(n)$

Visualization for 3×3 grid:

Row 0: dp = [1, 1, 1]  (from start, right moves)
Row 1: 
  j=0: dp[0] persists (1)
  j=1: obstacle → dp[1]=0
  j=2: dp[2] = dp[2](1) + dp[1](0) = 1
Row 2:
  j=0: dp[0] persists (1)
  j=1: dp[1] = dp[1](0) + dp[0](1) = 1
  j=2: dp[2] = dp[2](1) + dp[1](1) = 2
Result: 2

Approach 5: In-Place Modification (No Extra Space)

Concept: Use the input grid itself to store DP values (if allowed to modify input).

Pseudocode:

def uniquePathsWithObstacles(grid):
    m, n = len(grid), len(grid[0])
    
    if grid[0][0] == 1:
        return 0
    
    # Convert obstacle representation
    grid[0][0] = 1  # 1 now means "1 path here" (not obstacle)
    
    # First column: convert obstacles to 0, paths from above
    for i in range(1, m):
        grid[i][0] = 0 if grid[i][0] == 1 else grid[i-1][0]
    
    # First row: convert obstacles to 0, paths from left
    for j in range(1, n):
        grid[0][j] = 0 if grid[0][j] == 1 else grid[0][j-1]
    
    # Fill rest
    for i in range(1, m):
        for j in range(1, n):
            if grid[i][j] == 1:  # Original obstacle
                grid[i][j] = 0
            else:
                grid[i][j] = grid[i-1][j] + grid[i][j-1]
    
    return grid[m-1][n-1]

Complexity Proof:

• Time: $O(mn)$
• Space: $O(1)$ (modifies input in-place)

4. Code Deep Dive

Optimal Solution (1D DP) - Line-by-Line Analysis

def uniquePathsWithObstacles(obstacleGrid):
    # Extract dimensions
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    
    # Critical check: if start or end is blocked, immediately return 0
    # This handles Example 2's edge case where end might be blocked
    if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1:
        return 0
    
    # DP array: dp[j] = number of ways to reach current row, column j
    # Initialize with zeros
    dp = [0] * n
    
    # Starting cell: exactly 1 way to be here (if not obstacle, which we checked)
    dp[0] = 1  # Line 1: Base case initialization
    
    # Iterate through each cell in row-major order
    for i in range(m):  # Line 2: Process each row
        for j in range(n):  # Line 3: Process each column in current row
            
            # If current cell is an obstacle
            if obstacleGrid[i][j] == 1:  # Line 4: Obstacle detection
                dp[j] = 0  # Line 5: No paths can pass through obstacle
                # This zero propagates to cells that depend on this one
            
            # If current cell is not an obstacle AND not in first column
            elif j > 0:  # Line 6: Check if we can come from left
                # dp[j] currently stores paths from ABOVE (previous row)
                # dp[j-1] stores paths from LEFT (current row, previous column)
                dp[j] = dp[j] + dp[j-1]  # Line 7: Key recurrence relation
                
            # For first column (j=0): 
            # dp[0] persists from previous row if not obstacle
            # This handles the "only from above" case for first column
    
    # Final answer: number of ways to reach bottom-right corner
    return dp[n-1]  # Line 8: Return result

Edge Case Handling Map

Example/Edge Case	How Code Handles It
Example 1 ([[0,0,0],[0,1,0],[0,0,0]])	Line 4-5 detects obstacle at (1,1), sets dp[1]=0, preventing paths through it
Example 2 ([[0,1],[0,0]])	Line 1 check passes (start not blocked), line 4 sets dp[1]=0 in row 0, but dp[1] recalculated in row 1
Start blocked ([[1,...]])	Line 1 returns 0 immediately
End blocked ([...,[...,1]])	Line 1 returns 0 immediately
Single cell ([[0]])	Line 1 passes (not blocked), dp[0]=1, returns dp[0]=1
Single row with obstacle ([[0,1,0]])	Line 4 sets dp[1]=0, dp[2] becomes dp[2]+dp[1]=0+0=0, returns 0
Completely blocked row	Line 4 sets all dp entries to 0 in that row, propagates to 0 result

Memory Flow Visualization

Time step visualization for grid = [[0,0,0],[0,1,0],[0,0,0]]

Initial: dp = [1, 0, 0]

Row 0, Col 0: grid[0][0]=0, j=0 → dp persists: [1, 0, 0]
Row 0, Col 1: grid[0][1]=0, j>0 → dp[1]=dp[1](0)+dp[0](1)=1: [1, 1, 0]
Row 0, Col 2: grid[0][2]=0, j>0 → dp[2]=dp[2](0)+dp[1](1)=1: [1, 1, 1]

Row 1, Col 0: grid[1][0]=0, j=0 → dp[0] persists: [1, 1, 1]
Row 1, Col 1: grid[1][1]=1 → dp[1]=0: [1, 0, 1]
Row 1, Col 2: grid[1][2]=0, j>0 → dp[2]=dp[2](1)+dp[1](0)=1: [1, 0, 1]

Row 2, Col 0: grid[2][0]=0, j=0 → dp[0] persists: [1, 0, 1]
Row 2, Col 1: grid[2][1]=0, j>0 → dp[1]=dp[1](0)+dp[0](1)=1: [1, 1, 1]
Row 2, Col 2: grid[2][2]=0, j>0 → dp[2]=dp[2](1)+dp[1](1)=2: [1, 1, 2]

Result: dp[2] = 2

5. Complexity War Room

Hardware-Aware Analysis

Memory Hierarchy Analysis for 100×100 grid:

• Input size: $100 \times 100 = 10^4$ cells
• As integers (4 bytes each): $40$ KB
• 1D DP array (100 elements): $400$ bytes
• L1 Cache: Typically 32-64 KB → Entire DP array fits in L1 cache
• L2/L3 Cache: 256 KB to 32 MB → Entire grid fits comfortably

Performance Prediction:

• $10^4$ operations at ~1 ns each (CPU) = 10 μs theoretical minimum
• Actual: ~50-100 μs with Python overhead
• Memory bandwidth: ~40 KB read (grid) + negligible DP writes

Algorithmic Comparison on Modern Hardware:

Approach	Time Complexity	Space Complexity	Cache Efficiency	Practical Speed (est.)
Brute Force	$O(2^{m+n})$	$O(m+n)$	Poor (deep recursion)	∞ (never completes)
Memoized Top-Down	$O(mn)$	$O(mn)$ stack+table	Moderate	500 μs
2D Bottom-Up DP	$O(mn)$	$O(mn)$	Good (sequential access)	200 μs
1D DP (Optimal)	$O(mn)$	$O(n)$	Excellent (fits in L1)	100 μs
In-Place DP	$O(mn)$	$O(1)$	Good	150 μs

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability	Production Viability
Brute Force Recursion	$O(2^{m+n})$	$O(m+n)$	9/10 (simple)	❌ Fails large cases	❌ Never use
Memoized Recursion (Top-Down)	$O(mn)$	$O(mn)$	8/10 (clear logic)	✅ Good for explanation	⚠️ Stack overflow risk for large m,n
2D Table DP	$O(mn)$	$O(mn)$	10/10 (intuitive)	✅ Excellent teaching tool	⚠️ Memory heavy for huge grids
1D Array DP	$O(mn)$	$O(n)$	7/10 (needs explanation)	✅ Optimal answer expected	✅ Best for production
In-Place Modification	$O(mn)$	$O(1)$	6/10 (destructive)	⚠️ Only if modification allowed	⚠️ Destructive, not thread-safe

Scalability Projections

Grid Size	1D DP Time	1D DP Memory	2D DP Memory
10×10	<1 ms	40 bytes	400 bytes
100×100	~0.1 ms	400 bytes	40 KB
1000×1000	~10 ms	4 KB	4 MB
10000×10000	~1 second	40 KB	400 MB (problematic)

6. Pro Mode Extras

Variants & Extensions

Variant 1: Multiple Moving Directions (LeetCode 980)

Problem: Robot can move up, down, left, right, must visit all empty cells exactly once. Solution: Backtracking with pruning, $O(3^{mn})$ time, $O(mn)$ space.

Variant 2: Minimum Path Sum with Obstacles (LeetCode 64)

Problem: Each cell has a cost, find minimum cost path avoiding obstacles. Solution: DP with $dp[i][j] = \min(dp[i-1][j], dp[i][j-1]) + grid[i][j]$ if not obstacle.

Variant 3: Unique Paths III (LeetCode 980)

Problem: Must walk over every non-obstacle cell exactly once. Solution: DFS/backtracking counting all Hamiltonian paths.

Variant 4: k Obstacle Elimination

Problem: Can remove up to k obstacles. Solution: 3D DP: $dp[i][j][k]$ = paths to $(i,j)$ having removed $k$ obstacles.

Variant 5: Probabilistic Movement

Problem: Robot moves down with probability p, right with probability 1-p. Solution: DP where $dp[i][j] = p\cdot dp[i-1][j] + (1-p)\cdot dp[i][j-1]$.

Interview Cheat Sheet

Must-Mention Points

1. Immediate edge cases: “First, I’ll check if start or end cell is blocked.”
2. Complexity justification: “Since we only move down/right, we have optimal substructure.”
3. Space optimization insight: “We only need previous row, so we can use O(n) space.”
4. Obstacle handling: “Obstacles create zero-entries that propagate through DP.”

Common Interview Questions & Answers

• Q: “What if grid is huge (millions×millions)?” A: “We could use sparse DP only storing non-obstacle cells, or use combinatorial formulas between obstacles.”

• Q: “How to handle floating-point obstacles (probabilities)?” A: “Same DP structure but with multiplication instead of addition for probabilities.”

• Q: “What if we can move diagonally too?” A: “Add third term: $dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]$.”

Whiteboard Strategy

1. Draw a 3×3 grid with one obstacle
2. Show DP table filling process
3. Demonstrate space optimization from 2D to 1D
4. Walk through edge cases (start/end blocked, single row/column)

Testing Strategy

test_cases = [
    ([[0]], 1),  # Single cell
    ([[1]], 0),  # Single obstacle
    ([[0,1],[0,0]], 1),  # Example 2
    ([[0,0,0],[0,1,0],[0,0,0]], 2),  # Example 1
    ([[0,0],[0,0]], 2),  # 2x2 no obstacles
    ([[0,0,0,0],[0,1,0,0],[0,0,0,0],[0,0,1,0]], 7),  # Custom
]

Mathematical Insights

Combinatorial Formula Without Obstacles

For an $m\times n$ grid without obstacles:

$$\text{paths} = \binom{m+n-2}{m-1} = \frac{(m+n-2)!}{(m-1)!(n-1)!}$$

With Obstacles Using Inclusion-Exclusion

Let $O = \{\text{obstacle cells}\}$. Then:

$$\text{paths} = \sum_{k=0}^{|O|} (-1)^k \sum_{S \subseteq O, |S|=k} \text{paths through all cells in S}$$

But this is exponential in $|O|$, so DP is better.

Generating Function Approach

Number of paths avoiding obstacles equals coefficient of $x^{m-1}y^{n-1}$ in:

$$\prod_{i=0}^{m-1}\prod_{j=0}^{n-1} (1 + x\delta_{i+1,j} + y\delta_{i,j+1})^{\mathbb{1}_{\text{not obstacle}(i,j)}}$$

Where $\delta_{a,b}$ is 1 if move from a to b is valid. This is more theoretical than practical.

Production-Grade Implementation

from typing import List

class UniquePathsSolver:
    def __init__(self, grid: List[List[int]]):
        self.grid = grid
        self.m = len(grid)
        self.n = len(grid[0]) if self.m > 0 else 0
        self._validate_grid()
    
    def _validate_grid(self):
        """Validate input constraints."""
        if not 1 <= self.m <= 100:
            raise ValueError(f"m must be between 1 and 100, got {self.m}")
        if not 1 <= self.n <= 100:
            raise ValueError(f"n must be between 1 and 100, got {self.n}")
        for row in self.grid:
            if len(row) != self.n:
                raise ValueError("All rows must have same length")
            for val in row:
                if val not in (0, 1):
                    raise ValueError(f"Grid values must be 0 or 1, got {val}")
    
    def solve(self) -> int:
        """Main solver using 1D DP."""
        if self.grid[0][0] == 1 or self.grid[self.m-1][self.n-1] == 1:
            return 0
        
        dp = [0] * self.n
        dp[0] = 1
        
        for i in range(self.m):
            for j in range(self.n):
                if self.grid[i][j] == 1:
                    dp[j] = 0
                elif j > 0:
                    dp[j] += dp[j-1]
        
        return dp[self.n-1]
    
    def solve_2d(self) -> int:
        """Alternative 2D DP for comparison."""
        if self.grid[0][0] == 1 or self.grid[self.m-1][self.n-1] == 1:
            return 0
        
        dp = [[0] * self.n for _ in range(self.m)]
        dp[0][0] = 1
        
        for i in range(1, self.m):
            if self.grid[i][0] == 0:
                dp[i][0] = dp[i-1][0]
        
        for j in range(1, self.n):
            if self.grid[0][j] == 0:
                dp[0][j] = dp[0][j-1]
        
        for i in range(1, self.m):
            for j in range(1, self.n):
                if self.grid[i][j] == 0:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[self.m-1][self.n-1]

Final Recommendation: For interviews, explain the 2D DP first for clarity, then optimize to 1D DP. For production, use the 1D DP solution with proper input validation and error handling.