# LeetCode 63: Unique Paths II ## Problem Restatement A robot starts at the top-left corner of a grid. The robot wants to reach the bottom-right corner. At each step, the robot may move only: 1. Right 2. Down Some cells contain obstacles. If a cell contains an obstacle, the robot cannot move onto that cell. The grid uses: ```python 0 = empty cell 1 = obstacle ``` We need to count how many unique valid paths exist. The official constraints are `1 <= m, n <= 100`. ([leetcode.com](https://leetcode.com/problems/unique-paths-ii/?utm_source=chatgpt.com)) ## Input and Output | Item | Meaning | |---|---| | Input | A grid called `obstacleGrid` | | Output | Number of unique paths | | `0` | Empty cell | | `1` | Obstacle | | Allowed moves | Right or down | Function shape: ```python def uniquePathsWithObstacles( obstacleGrid: list[list[int]] ) -> int: ... ``` ## Examples For: ```python obstacleGrid = [ [0,0,0], [0,1,0], [0,0,0], ] ``` The obstacle is in the center: ```text . . . . X . . . . ``` There are two valid paths: ```text Right -> Right -> Down -> Down Down -> Down -> Right -> Right ``` So the answer is: ```python 2 ``` For: ```python obstacleGrid = [ [0,1], [0,0], ] ``` The robot cannot move right from the start because of the obstacle. Only one valid path exists: ```text Down -> Right ``` So the answer is: ```python 1 ``` ## First Thought: Recursive Search A direct recursive approach is: From each cell: 1. Move right 2. Move down Stop when: - We leave the grid - We hit an obstacle This works logically, but many recursive calls recompute the same cells repeatedly. We need dynamic programming. ## Key Insight Without obstacles, the number of paths to a cell equals: ```python paths from above + paths from left ``` The same idea still works here. The only difference is: If a cell is blocked, the number of paths to it is zero. So: ```python if obstacle: dp[row][col] = 0 else: dp[row][col] = dp[row - 1][col] + dp[row][col - 1] ``` ## Base Cases The start cell matters. If the start cell is blocked: ```python obstacleGrid[0][0] == 1 ``` then no path exists. The first row and first column also need careful handling. Once an obstacle appears in the first row, every cell after it becomes unreachable because the robot can only move right. The same idea applies to the first column. ## Algorithm Create a DP table: ```python dp = [[0] * n for _ in range(m)] ``` If the start cell is blocked, return `0`. Otherwise: ```python dp[0][0] = 1 ``` Then fill the table. For each cell: 1. If it is an obstacle, set paths to `0`. 2. Otherwise, add paths from above and left. Return: ```python dp[m - 1][n - 1] ``` ## Correctness The robot may move only right or down. Therefore every path reaching cell `(row, col)` must come either from `(row - 1, col)` or `(row, col - 1)`. If `(row, col)` contains an obstacle, the robot cannot stand on that cell. So the number of paths to that cell must be zero. Otherwise, every valid path to `(row, col)` comes from either above or left. These two sets of paths are disjoint because the final move differs. Therefore the total number of paths equals the sum of the number of paths from those two neighboring cells. The algorithm initializes the starting cell correctly and fills the table row by row using already-correct earlier values. Therefore every DP value becomes correct, including the bottom-right corner. ## Complexity | Metric | Value | Why | |---|---|---| | Time | `O(m * n)` | Every cell is processed once | | Space | `O(m * n)` | The DP table stores all cells | ## Implementation ```python class Solution: def uniquePathsWithObstacles( self, obstacleGrid: list[list[int]], ) -> int: m = len(obstacleGrid) n = len(obstacleGrid[0]) dp = [[0] * n for _ in range(m)] if obstacleGrid[0][0] == 1: return 0 dp[0][0] = 1 for row in range(m): for col in range(n): if obstacleGrid[row][col] == 1: dp[row][col] = 0 else: if row > 0: dp[row][col] += dp[row - 1][col] if col > 0: dp[row][col] += dp[row][col - 1] return dp[m - 1][n - 1] ``` ## Code Explanation First get the grid dimensions: ```python m = len(obstacleGrid) n = len(obstacleGrid[0]) ``` Create the DP table: ```python dp = [[0] * n for _ in range(m)] ``` If the starting cell is blocked, no path exists: ```python if obstacleGrid[0][0] == 1: return 0 ``` Otherwise initialize: ```python dp[0][0] = 1 ``` Now process every cell: ```python for row in range(m): for col in range(n): ``` If the current cell is blocked: ```python if obstacleGrid[row][col] == 1: dp[row][col] = 0 ``` Otherwise, add paths from above: ```python if row > 0: dp[row][col] += dp[row - 1][col] ``` and from the left: ```python if col > 0: dp[row][col] += dp[row][col - 1] ``` Finally return: ```python return dp[m - 1][n - 1] ``` ## Space Optimization We only need the current row. So we can reduce space to `O(n)`. The transition becomes: ```python dp[col] += dp[col - 1] ``` If a cell contains an obstacle: ```python dp[col] = 0 ``` ## Optimized Implementation ```python class Solution: def uniquePathsWithObstacles( self, obstacleGrid: list[list[int]], ) -> int: m = len(obstacleGrid) n = len(obstacleGrid[0]) dp = [0] * n dp[0] = 1 for row in range(m): for col in range(n): if obstacleGrid[row][col] == 1: dp[col] = 0 elif col > 0: dp[col] += dp[col - 1] return dp[-1] ``` ## Testing ```python def run_tests(): s = Solution() assert s.uniquePathsWithObstacles([ [0,0,0], [0,1,0], [0,0,0], ]) == 2 assert s.uniquePathsWithObstacles([ [0,1], [0,0], ]) == 1 assert s.uniquePathsWithObstacles([ [1], ]) == 0 assert s.uniquePathsWithObstacles([ [0], ]) == 1 assert s.uniquePathsWithObstacles([ [0,0], [1,1], [0,0], ]) == 0 assert s.uniquePathsWithObstacles([ [0,0,0], [0,0,0], ]) == 3 print("all tests passed") run_tests() ``` | Test | Why | |---|---| | Center obstacle example | Official example | | Small obstacle example | Only one valid path | | Blocked start | No valid path | | Single empty cell | One valid path | | Fully blocked middle row | Impossible to reach finish | | No obstacles | Matches standard Unique Paths problem |