Unique Paths with Obstacles

Count the number of paths from top-left to bottom-right, avoiding obstacles in a grid.

dynamic-programming grid 2d-array paths

Write a function `unique_paths_with_obstacles(grid)` that takes a 2D list of integers as input. Each cell in `grid` is either 0 (free) or 1 (obstacle). The robot starts at the top-left corner (0,0) and wants to go to the bottom-right corner. It can only move down or right. Count how many unique paths exist from start to end, avoiding obstacles. If the start or end cell is an obstacle, return 0. The result is guaranteed to fit in a 64-bit integer (Python int is fine).

Implement the function exactly with this signature.

Input constraints:
- 1 ≤ rows, cols ≤ 30
- grid values are only 0 or 1.
- The total number of cells is at most 900.

Complexity requirement: O(rows * cols) time and O(rows * cols) space.

Constraints

- 1 ≤ rows, cols ≤ 30
- grid[i][j] ∈ {0, 1}
- The answer fits in a Python int.
- Do not import any external libraries.

Complexity: O(R*C) time, O(R*C) space (or O(min(R,C)) space if you prefer).

Example

>>> grid = [[0,0,0],[0,1,0],[0,0,0]]
>>> unique_paths_with_obstacles(grid)
2
>>> grid = [[0,1],[0,0]]
>>> unique_paths_with_obstacles(grid)
1
>>> grid = [[1,0],[0,0]]
>>> unique_paths_with_obstacles(grid)
0

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Initialize the first row and column carefully: if an obstacle appears, all cells after it are unreachable.

Use a 2D DP table where dp[i][j] is the number of ways to reach (i,j). The value is 0 if there's an obstacle at that cell.

For free cells, dp[i][j] = dp[i-1][j] + dp[i][j-1], but handle the boundaries for the first row and column.

You can optimize space to a 1D array by reusing a row, but it's not required for correctness.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.