Problem Description

You have a robot placed on an m x n grid, where the robot starts at the top-left corner position grid[0][0]. The robot's goal is to reach the bottom-right corner position grid[m-1][n-1].

The robot has movement restrictions:

• It can only move in two directions: either down (to the next row) or right (to the next column)
• It cannot move up or left
• It cannot move diagonally

The grid contains obstacles and empty spaces:

• A cell with value 1 represents an obstacle that blocks the robot's path
• A cell with value 0 represents an empty space where the robot can move through

The robot must find a path from start to finish without passing through any obstacles. Your task is to calculate the total number of unique paths the robot can take to reach the destination.

For example, if the robot is at position (i, j), it can only move to:

• Position (i+1, j) - moving down
• Position (i, j+1) - moving right

But only if those positions are within the grid boundaries and don't contain obstacles.

The function should return the total count of all possible unique paths. If there's no valid path (due to obstacles blocking all routes), it should return 0.

Intuition

When thinking about how to count all possible paths, we can observe that this is a classic dynamic programming problem. The key insight is that the number of ways to reach any cell is the sum of ways to reach it from the cells that can lead to it.

Since the robot can only move down or right, any cell (i, j) can only be reached from:

• The cell above it (i-1, j) by moving down
• The cell to its left (i, j-1) by moving right

This means if we know the number of paths to reach (i-1, j) and (i, j-1), we can calculate the paths to (i, j) by simply adding them together: paths[i][j] = paths[i-1][j] + paths[i][j-1].

However, we need to handle obstacles - if a cell contains an obstacle (value 1), there are 0 ways to reach the destination through that cell.

We can solve this problem recursively by breaking it down:

• From any position (i, j), the robot has two choices: go down to (i+1, j) or go right to (i, j+1)
• The total paths from (i, j) equals the sum of paths from these two next positions
• We work backwards from the destination, asking "how many ways can I reach the end from here?"

The base cases are:

• If we're out of bounds or hit an obstacle, return 0 (no valid path)
• If we're at the destination (m-1, n-1), return 1 (we found one valid path)

To avoid recalculating the same subproblems multiple times (since many paths might pass through the same cell), we use memoization with the @cache decorator. This stores previously computed results and reuses them when needed, making our solution efficient.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses a memoization search (also known as top-down dynamic programming) approach with depth-first search (DFS).

We implement a recursive function dfs(i, j) that calculates the number of unique paths from position (i, j) to the destination (m-1, n-1).

Function Logic:

The dfs(i, j) function follows these steps:

1. Boundary and Obstacle Check:
   • If i >= m or j >= n (out of bounds), return 0
   • If obstacleGrid[i][j] == 1 (obstacle present), return 0
2. Destination Check:
   • If i == m-1 and j == n-1 (reached destination), return 1
3. Recursive Case:
   • Calculate paths by moving down: dfs(i+1, j)
   • Calculate paths by moving right: dfs(i, j+1)
   • Return the sum: dfs(i+1, j) + dfs(i, j+1)

Memoization with @cache:

The @cache decorator automatically stores the results of dfs(i, j) for each unique (i, j) pair. When the same position is encountered again, the cached result is returned immediately instead of recalculating. This optimization reduces the time complexity from exponential to O(m × n).

Implementation Flow:

1. Extract grid dimensions: m = len(obstacleGrid) and n = len(obstacleGrid[0])
2. Start the recursive search from the top-left corner: dfs(0, 0)
3. The function explores all possible paths while avoiding obstacles
4. The memoization ensures each cell is computed only once
5. Return the total number of unique paths found

This approach efficiently handles the obstacle constraints while counting all valid paths from start to finish.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider a 3×3 grid with one obstacle:

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

Where 0 = empty space, 1 = obstacle

Step-by-step execution of dfs(0, 0):

1. Start at (0,0): Not out of bounds, no obstacle, not at destination

   • Need to calculate: dfs(1, 0) + dfs(0, 1)

2. Branch 1: Calculate dfs(1, 0) (moving down from start)

   • Not out of bounds, no obstacle, not at destination
   • Need to calculate: dfs(2, 0) + dfs(1, 1)

   2a. Calculate dfs(2, 0): - Need: dfs(3, 0) + dfs(2, 1) - dfs(3, 0) = 0 (out of bounds) - dfs(2, 1) needs calculation (see below)

   2b. Calculate dfs(1, 1): - Returns 0 (obstacle at position [1][1])

3. Branch 2: Calculate dfs(0, 1) (moving right from start)

   • Not out of bounds, no obstacle, not at destination
   • Need to calculate: dfs(1, 1) + dfs(0, 2)

   3a. dfs(1, 1) = 0 (already cached - obstacle)

   3b. Calculate dfs(0, 2): - Need: dfs(1, 2) + dfs(0, 3) - dfs(0, 3) = 0 (out of bounds) - dfs(1, 2) needs calculation

4. Continue exploring valid paths...

   • dfs(1, 2) → leads to dfs(2, 2) (destination) = 1
   • dfs(2, 1) → leads to dfs(2, 2) (destination) = 1

Path visualization:

• Path 1: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) ✓
• Path 2: (0,0) → (0,1) → (1,0) → (2,0) → (2,1) → (2,2) ✓
• Invalid: Any path through (1,1) is blocked by obstacle ✗

Memoization in action:

• When we first calculate dfs(1, 1), it returns 0 due to the obstacle
• Later calls to dfs(1, 1) immediately return the cached value 0
• Similarly, dfs(2, 2) is calculated once as 1 (destination reached) and cached

Final result: dfs(0, 0) returns 2, indicating there are exactly 2 unique paths from start to finish while avoiding the obstacle.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The solution uses a depth-first search (DFS) with memoization via the @cache decorator. Each cell (i, j) in the grid is visited at most once due to memoization. When we reach a cell for the first time, we compute its result and cache it. Any subsequent calls to the same cell will return the cached result in O(1) time. Since there are m × n cells in total, and each cell requires O(1) work (aside from the recursive calls), the overall time complexity is O(m × n).

Space Complexity: O(m × n)

The space complexity consists of two components:

1. Cache storage: The @cache decorator stores the result for each unique (i, j) pair. In the worst case, we may need to store results for all m × n cells, requiring O(m × n) space.
2. Recursion stack: In the worst case, the recursion depth can go up to m + n - 1 (when traversing from top-left to bottom-right corner), which requires O(m + n) stack space.

Since O(m × n) dominates O(m + n), the overall space complexity is O(m × n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Checking if Start or End Position is Blocked

One of the most common mistakes is forgetting to handle edge cases where the starting position (0, 0) or ending position (m-1, n-1) contains an obstacle. If either of these critical positions is blocked, there's no valid path possible, but the recursive solution might not handle this explicitly.

Problem Example:

obstacleGrid = [[1, 0],  # Start position blocked!
                 [0, 0]]
# Or
obstacleGrid = [[0, 0],
                 [0, 1]]  # End position blocked!

Solution: Add an early return check before starting the DFS:

def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
    rows = len(obstacleGrid)
    cols = len(obstacleGrid[0])
  
    # Early return if start or end is blocked
    if obstacleGrid[0][0] == 1 or obstacleGrid[rows-1][cols-1] == 1:
        return 0
  
    # Continue with DFS...

2. Stack Overflow with Large Grids

Python has a default recursion limit (typically 1000), and for large grids, the recursive DFS approach can hit this limit, causing a RecursionError. A grid of size 100×100 could potentially require deep recursion.

Solution: Either increase the recursion limit or use an iterative DP approach:

import sys
sys.setrecursionlimit(10000)  # Increase limit

# Or better: Use bottom-up DP instead
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
    rows, cols = len(obstacleGrid), len(obstacleGrid[0])
    if obstacleGrid[0][0] == 1 or obstacleGrid[rows-1][cols-1] == 1:
        return 0
  
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = 1
  
    # Fill first row
    for j in range(1, cols):
        dp[0][j] = dp[0][j-1] if obstacleGrid[0][j] == 0 else 0
  
    # Fill first column
    for i in range(1, rows):
        dp[i][0] = dp[i-1][0] if obstacleGrid[i][0] == 0 else 0
  
    # Fill rest of the grid
    for i in range(1, rows):
        for j in range(1, cols):
            if obstacleGrid[i][j] == 0:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
  
    return dp[rows-1][cols-1]

3. Memory Issues with @cache Decorator

The @cache decorator stores all computed results indefinitely, which can cause memory issues for very large grids or when the function is called multiple times with different grids in a testing environment.

Solution: Clear the cache after each function call or use @lru_cache with a size limit:

from functools import lru_cache

@lru_cache(maxsize=128)  # Limited cache size
def dfs(row: int, col: int) -> int:
    # ... function body ...

# Or clear cache after use:
result = dfs(0, 0)
dfs.cache_clear()  # Clear the cache
return result

4. Integer Overflow for Large Path Counts

While Python handles arbitrary precision integers automatically, in other languages or when interfacing with systems expecting fixed-size integers, the path count might overflow for large grids without obstacles.

Solution: If needed, return the result modulo a large prime number:

MOD = 10**9 + 7
return (paths_going_down + paths_going_right) % MOD