63. Unique Paths II
Model: qwen3.5:9b
Topics: Array,Dynamic Programming
FAANG asked: 1
Acceptance rate: 35.4%
Problem Breakdown
We need to calculate the number of unique paths from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1). The robot can only move Down or Right. Some cells are blocked by obstacles (marked 1), while free space is marked 0.
- Inputs: A 2D integer array
obstacleGrid, where dimensions and satisfy . - Outputs: An integer representing the count of valid unique paths.
- Implicit Constraints/Edge Cases:
- If the start or end cell is an obstacle (
1), no path exists (return0). - The result can grow large, but Python handles arbitrary precision integers automatically, so overflow isn’t a concern here compared to languages like C++ or Java.
- If the start or end cell is an obstacle (
Intuition
A brute-force approach using recursion with backtracking would explore every possible combination of moves. In the worst case (no obstacles), there are paths roughly. For grid sizes up to 100x100, this exponential time complexity is unacceptable and will lead to a Time Limit Exceeded error.
The key insight for Dynamic Programming here is that the number of ways to reach any cell (i, j) depends entirely on how many ways we could reach its immediate predecessors:
- The cell directly above it
(i-1, j). - The cell directly to the left
(i, j-1).
If a cell contains an obstacle (1), there are 0 paths reaching that specific cell. If it is free space (0), we sum the valid paths coming from above and left. This overlapping substructure allows us to build up the solution iteratively in linear time relative to grid size.
Approach
We will use a 2D DP table of the same dimensions as obstacleGrid, initialized with zeros.
- Initialization: Check if the start cell
(0, 0)is an obstacle. If so, return0immediately since no path can exist. Otherwise, setdp[0][0] = 1. - Boundary Handling (First Row/Col): For cells in the first row or column, they only have one valid neighbor (either from above for rows > 0, or from left for cols > 0). If a cell is an obstacle, all subsequent paths through that line are blocked (
dpvalue remains0). - Iteration: Iterate through every other cell
(i, j)in the grid:- If
obstacleGrid[i][j] == 1, setdp[i][j] = 0. - Otherwise, calculate
dp[i][j]as sum of valid paths from top (dp[i-1][j]) and left (dp[i][j-1]). Note: Check bounds to ensure we don’t access negative indices.
- If
Complexity Analysis
- Time Complexity: . We visit each cell in the grid exactly once, performing constant time arithmetic operations at each step. Given constraints (), this is well within limits.
- Space Complexity: for the DP table. This can be optimized to by using a single row array since we only need data from the current and previous rows, but given the constraints here, readability takes precedence over space optimization unless explicitly requested.
Solution
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
# Handle edge case where start or end is an obstacle immediately
m = len(obstacleGrid)
n = len(obstacleGrid[0])
if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1:
return 0
# Initialize DP table with zeros.
# We can reuse the input grid to save space, but creating a new one is clearer for explanation.
dp = [[0] * n for _ in range(m)]
# Base case: Start position has 1 path (the robot itself) if not obstacle
dp[0][0] = 1
# Fill first column: can only come from above
for i in range(1, m):
if obstacleGrid[i][0] == 1:
break
else:
dp[i][0] = dp[i-1][0]
# Fill first row: can only come from left
for j in range(1, n):
if obstacleGrid[0][j] == 1:
break
else:
dp[0][j] = dp[0][j-1]
# Iterate through the rest of the grid
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]
Edge Cases Handled
- Obstacle at Start/End: The code checks
obstacleGrid[0][0]andobstacleGrid[m-1][n-1]. If either is1, it returns0immediately. This prevents incorrect path counting or index errors in the DP logic. - Single Row or Column: The loops for filling rows/cols handle this naturally (one of the nested loop ranges will be empty, and boundary checks ensure we don’t access out-of-bounds neighbors). If a single row has an obstacle,
dpvalues after that point become 0 correctly due to the break logic. - All Obstacles: The loops set all reachable cells in DP table to 0 if obstacles are encountered; final result returns 0 as expected.