Full lesson preview

Count unique paths with obstacles

Compute number of unique paths from top-left to bottom-right in a grid with obstacles using DP.

Python practice15 minDynamic ProgrammingIntermediateLast updated March 29, 2026

Problem statement

Given a 2D grid where 0 represents an empty cell and 1 represents an obstacle, return the number of unique paths from the top-left corner (0,0) to the bottom-right corner (m-1,n-1). You may only move either down or right at any point in time. If the start or end cell is blocked, return 0. Implement unique_paths_with_obstacles(grid) that takes a list of lists of integers and returns the count of unique paths (an integer).

Task

Implement a function that counts unique grid paths avoiding obstacles using tabulation.

Examples

Example with an obstacle

Input

unique_paths_with_obstacles([[0,0,0],[0,1,0],[0,0,0]])

Output

There are two paths that avoid the obstacle at (1,1).

Input format

A list of lists of integers grid where grid[i][j] is 0 (empty) or 1 (obstacle). Dimensions m x n, m,n >= 1.

Output format

An integer representing the number of unique paths from top-left to bottom-right.

Constraints

1 <= m, n <= 100; grid elements are 0 or 1. Aim for O(m*n) time and O(n) extra space.

Samples

Sample 1

Input

[[0,1],[0,0]]

Output

Only one path: down then right.