Domain 2MediumCORE

Unique Paths II

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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Dynamic Programming

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 mm and nn satisfy 1≤m,n≤1001 \le m, n \le 100.
  • 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 (return 0).
    • 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.

Intuition

A brute-force approach using recursion with backtracking would explore every possible combination of moves. In the worst case (no obstacles), there are 2m+n2^{m+n} 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.

  1. Initialization: Check if the start cell (0, 0) is an obstacle. If so, return 0 immediately since no path can exist. Otherwise, set dp[0][0] = 1.
  2. 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 (dp value remains 0).
  3. Iteration: Iterate through every other cell (i, j) in the grid:
    • If obstacleGrid[i][j] == 1, set dp[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.

Complexity Analysis

  • Time Complexity: O(m×n)O(m \times n). We visit each cell in the grid exactly once, performing constant time arithmetic operations at each step. Given constraints (m,n≤100m,n \le 100), this is well within limits.
  • Space Complexity: O(m×n)O(m \times n) for the DP table. This can be optimized to O(n)O(n) 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] and obstacleGrid[m-1][n-1]. If either is 1, it returns 0 immediately. 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, dp values 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.