LeetCode 63 - Unique Paths II

This problem asks us to count how many different valid paths exist for a robot moving through a grid while avoiding obstacles. The robot starts in the top-left corner of the grid at position (0, 0) and wants to reach the bottom-right corner at position (m - 1, n - 1).

leetcodemediumarraydynamic-programmingmatrix

LeetCode Problem 63

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

This problem asks us to count how many different valid paths exist for a robot moving through a grid while avoiding obstacles.

The robot starts in the top-left corner of the grid at position (0, 0) and wants to reach the bottom-right corner at position (m - 1, n - 1). The robot can only move in two directions:

  • Right
  • Down

The grid contains two kinds of cells:

  • 0 represents an open space where the robot can move.
  • 1 represents an obstacle that blocks movement.

A valid path must never pass through an obstacle.

In simpler terms, we need to determine how many unique ways exist to move from the start to the destination while only moving right or down and avoiding blocked cells.

The input is a two-dimensional matrix obstacleGrid with dimensions m x n, where:

  • m is the number of rows.
  • n is the number of columns.

The expected output is a single integer representing the number of unique valid paths.

The constraints tell us several important things:

  • 1 <= m, n <= 100, meaning the grid can contain up to 10,000 cells.
  • Since brute force path exploration grows exponentially, we need something significantly more efficient.
  • The result is guaranteed to fit within a 32-bit integer (<= 2 * 10^9), so integer overflow is not a concern in Python, and it is safe in Go using int.

There are several important edge cases that can easily break a naive implementation:

  • The starting position may contain an obstacle. If grid[0][0] == 1, there are zero valid paths immediately.
  • The destination cell may contain an obstacle. If grid[m - 1][n - 1] == 1, no path can reach it.
  • A row or column may become completely blocked, preventing further movement.
  • Small grids such as 1 x 1 require careful handling. If the only cell is open, the answer is 1. If blocked, the answer is 0.

These edge cases strongly suggest using a structured counting strategy rather than recursively exploring every path.

Approaches

Brute Force Approach

A straightforward solution is to explore every possible path using recursion or depth-first search.

Starting from (0, 0), we recursively try:

  • Moving right
  • Moving down

Whenever we hit an obstacle or go out of bounds, we stop exploring that path. Whenever we reach the bottom-right corner, we count one valid path.

This approach is correct because it explicitly enumerates every possible route and counts only valid ones.

However, it becomes extremely slow because many subproblems are repeated. For example, multiple routes may arrive at the same cell, and each time we recompute the number of paths from that cell to the destination.

Without optimization, the number of recursive calls grows exponentially.

Key Insight for an Optimal Solution

The important observation is that the number of ways to reach a cell depends only on the number of ways to reach the cell directly above it and the cell directly to its left.

If a cell is open:

$$dp[row][col] = dp[row - 1][col] + dp[row][col - 1]$$

This works because the robot can only move down or right, meaning every path into a cell must come from one of those two directions.

If a cell contains an obstacle:

$$dp[row][col] = 0$$

because no path can pass through it.

This overlapping subproblem structure makes dynamic programming the ideal approach.

We can build a DP table where each entry stores the number of ways to reach that cell.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(m+n)) O(m+n) Recursively explores every possible path
Optimal Dynamic Programming O(m × n) O(m × n) Computes each cell once using previous results

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

  1. Handle impossible starting conditions

First, check whether the starting cell contains an obstacle.

If obstacleGrid[0][0] == 1, return 0 immediately because the robot cannot even begin moving. 2. Initialize the DP table

Create a dp matrix of the same size as the input grid.

Each dp[row][col] represents the number of unique ways to reach that position.

Initially, fill everything with 0. 3. Initialize the starting position

Since the robot begins at (0, 0), set:

dp[0][0] = 1

This represents one valid way to stand at the starting cell. 4. Iterate through every cell

Traverse the grid row by row.

For each cell:

  • If it contains an obstacle, set its value to 0.

  • Otherwise, compute paths from:

  • the top cell

  • the left cell

  1. Compute transitions

For every open cell (row, col):

  • Add paths from above if row > 0
  • Add paths from the left if col > 0

Conceptually:

dp[row][col] =
    paths from above +
    paths from left
  1. Return the final answer

The bottom-right cell stores the total number of valid paths.

Return:

dp[m - 1][n - 1]

Why it works

The algorithm maintains the invariant that dp[row][col] always equals the number of valid ways to reach that position.

Since movement is restricted to right and down, every valid path into a cell must come from exactly one of two places: the cell above or the cell to the left. By summing those already computed values, we correctly count every possible route exactly once. Obstacles naturally contribute zero paths, preventing invalid routes from affecting later computations.

Because we process the grid from top-left to bottom-right, every dependency is already computed before it is needed.

Python Solution

from typing import List

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        rows = len(obstacleGrid)
        cols = len(obstacleGrid[0])

        # If the starting cell is blocked, no path exists
        if obstacleGrid[0][0] == 1:
            return 0

        dp = [[0] * cols for _ in range(rows)]
        dp[0][0] = 1

        for row in range(rows):
            for col in range(cols):
                # Skip the starting cell
                if row == 0 and col == 0:
                    continue

                # Obstacle cell
                if obstacleGrid[row][col] == 1:
                    dp[row][col] = 0
                    continue

                paths_from_top = dp[row - 1][col] if row > 0 else 0
                paths_from_left = dp[row][col - 1] if col > 0 else 0

                dp[row][col] = paths_from_top + paths_from_left

        return dp[rows - 1][cols - 1]

The implementation closely follows the algorithm described earlier.

We begin by computing the grid dimensions and immediately handle the case where the starting position is blocked. If the robot cannot start, the answer is instantly 0.

Next, we create a dynamic programming matrix dp initialized with zeros. The starting position is assigned 1, representing one valid way to stand at the initial cell.

We then iterate through the grid row by row. For every position:

  • If the cell is blocked, we assign 0.
  • Otherwise, we compute the number of ways to reach it by summing the number of paths from the top and left neighboring cells.

The conditional expressions safely handle boundary conditions for the first row and first column, where one of the neighbors may not exist.

Finally, the bottom-right value is returned because it contains the total number of valid paths to the destination.

Go Solution

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	rows := len(obstacleGrid)
	cols := len(obstacleGrid[0])

	// If the starting cell is blocked
	if obstacleGrid[0][0] == 1 {
		return 0
	}

	dp := make([][]int, rows)
	for i := range dp {
		dp[i] = make([]int, cols)
	}

	dp[0][0] = 1

	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			// Skip starting cell
			if row == 0 && col == 0 {
				continue
			}

			// Obstacle cell
			if obstacleGrid[row][col] == 1 {
				dp[row][col] = 0
				continue
			}

			pathsFromTop := 0
			pathsFromLeft := 0

			if row > 0 {
				pathsFromTop = dp[row-1][col]
			}

			if col > 0 {
				pathsFromLeft = dp[row][col-1]
			}

			dp[row][col] = pathsFromTop + pathsFromLeft
		}
	}

	return dp[rows-1][cols-1]
}

The Go implementation follows the same logic as the Python version.

A two-dimensional slice is allocated to store DP values. Since Go does not support Python-style list comprehensions, each row must be initialized separately using make.

Boundary conditions are handled explicitly using conditional checks before accessing neighboring cells. Since the problem guarantees the answer fits inside 2 * 10^9, using Go's int type is safe.

Unlike Python, Go does not distinguish between None and empty slices in this problem, so no additional nil handling is required because the constraints guarantee valid input dimensions.

Worked Examples

Example 1

Input

obstacleGrid = [
    [0,0,0],
    [0,1,0],
    [0,0,0]
]

We initialize:

dp = [
    [1,0,0],
    [0,0,0],
    [0,0,0]
]

We process each cell:

Cell Action DP State
(0,1) From left = 1 [1,1,0]
(0,2) From left = 1 [1,1,1]
(1,0) From top = 1 second row becomes [1,0,0]
(1,1) Obstacle second row remains [1,0,0]
(1,2) Top = 1, Left = 0 second row becomes [1,0,1]
(2,0) From top = 1 third row becomes [1,0,0]
(2,1) Top = 0, Left = 1 third row becomes [1,1,0]
(2,2) Top = 1, Left = 1 third row becomes [1,1,2]

Final DP table:

0 1 2
0 1 1 1
1 1 0 1
2 1 1 2

Answer:

2

Example 2

Input

obstacleGrid = [
    [0,1],
    [0,0]
]

Initial state:

dp = [
    [1,0],
    [0,0]
]

Processing:

Cell Action DP State
(0,1) Obstacle [1,0]
(1,0) From top = 1 [1,0]
(1,1) Top = 0, Left = 1 [1,1]

Final DP table:

0 1
0 1 0
1 1 1

Answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(m × n) Every grid cell is processed exactly once
Space O(m × n) A DP table of the same size as the grid is stored

The time complexity is linear in the number of cells because we visit each cell once and perform constant work at each position.

The space complexity is also O(m × n) because we maintain a DP matrix storing the number of ways to reach every position. Although an O(n) optimization exists using a one-dimensional DP array, the full matrix version is easier to understand and aligns well with the problem explanation.

Test Cases

solution = Solution()

assert solution.uniquePathsWithObstacles(
    [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
) == 2  # Example 1

assert solution.uniquePathsWithObstacles(
    [[0, 1], [0, 0]]
) == 1  # Example 2

assert solution.uniquePathsWithObstacles(
    [[0]]
) == 1  # Single open cell

assert solution.uniquePathsWithObstacles(
    [[1]]
) == 0  # Single blocked cell

assert solution.uniquePathsWithObstacles(
    [[1, 0]]
) == 0  # Blocked starting cell

assert solution.uniquePathsWithObstacles(
    [[0, 1]]
) == 0  # Blocked destination cell

assert solution.uniquePathsWithObstacles(
    [[0, 0, 0, 0]]
) == 1  # Single row

assert solution.uniquePathsWithObstacles(
    [[0], [0], [0]]
) == 1  # Single column

assert solution.uniquePathsWithObstacles(
    [[0, 1, 0]]
) == 0  # Row blocked by obstacle

assert solution.uniquePathsWithObstacles(
    [[0], [1], [0]]
) == 0  # Column blocked by obstacle

assert solution.uniquePathsWithObstacles(
    [[0, 0], [0, 0]]
) == 2  # Simple 2x2 grid

assert solution.uniquePathsWithObstacles(
    [[0, 0, 0], [1, 1, 0], [0, 0, 0]]
) == 1  # Narrow valid path
Test Why
[[0,0,0],[0,1,0],[0,0,0]] Validates obstacle handling in the middle
[[0,1],[0,0]] Confirms alternate route works
[[0]] Smallest valid grid
[[1]] Smallest blocked grid
[[1,0]] Blocked starting position
[[0,1]] Blocked ending position
[[0,0,0,0]] Single row movement
[[0],[0],[0]] Single column movement
[[0,1,0]] Obstacle fully blocks progress
[[0],[1],[0]] Vertical blockage
[[0,0],[0,0]] Small grid with multiple routes
[[0,0,0],[1,1,0],[0,0,0]] Confirms DP handles constrained pathing

Edge Cases

Starting Cell Is Blocked

If obstacleGrid[0][0] == 1, the robot cannot move at all. A naive implementation might still initialize the starting cell as reachable and accidentally count invalid paths.

This implementation explicitly checks the starting cell before any computation and immediately returns 0.

Destination Cell Is Blocked

If the bottom-right cell contains an obstacle, reaching the goal is impossible.

Some implementations fail to account for this directly and may accidentally propagate values into the destination. In this solution, obstacle cells are always assigned 0, so the destination naturally becomes unreachable.

Single Cell Grid

A 1 x 1 grid is a special case because the robot starts and ends at the same position.

If the only cell is open (0), there is exactly one valid path, the robot simply stays where it is. If blocked (1), there are zero paths.

The implementation handles this naturally through initialization:

  • Open cell → dp[0][0] = 1
  • Blocked cell → immediate return 0

Entire Path Becomes Blocked

Sometimes a row or column obstacle configuration completely prevents progress.

For example:

[
    [0,1,0]
]

The robot cannot move past the obstacle because movement is restricted to right and down.

The DP logic correctly propagates zeros after blocked cells, ensuring impossible regions remain unreachable.