{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsMy spaceBlog
Ctrl + K
Ask AI

Unique Paths II – Solution & Complexity

Interview solutions
/
Unique Paths II

Solution Walkthrough

1. Set up the grid recurrence

  • Let ways[r][c] be the number of obstacle-free paths that reach cell (r, c).
  • You can only arrive from the cell above or the cell to the left, so ways[r][c] = ways[r-1][c] + ways[r][c-1].
  • An obstacle cell is unreachable, so its count is 0.

2. Fill a full 2D table

  • Seed the start cell with 1 unless it is an obstacle.
  • Sweep every cell in row-major order, zeroing obstacles and summing the reachable neighbors otherwise.
  • The answer sits in the bottom-right cell.
def unique_paths_with_obstacles(obstacle_grid: list[list[int]]) -> int:
    rows = len(obstacle_grid)
    cols = len(obstacle_grid[0])
    dp = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if obstacle_grid[r][c] == 1:
                dp[r][c] = 0
            elif r == 0 and c == 0:
                dp[r][c] = 1
            else:
                ways = 0
                if r > 0:
                    ways += dp[r - 1][c]
                if c > 0:
                    ways += dp[r][c - 1]
                dp[r][c] = ways
    return dp[rows - 1][cols - 1]

3. Reuse a single rolling row

  • When you process row by row, dp[c] already holds the count from the row above, and dp[c-1] holds the freshly updated count from the left.
  • So a single 1D array of width cols is enough: dp[c] += dp[c-1] for open cells, dp[c] = 0 for obstacles.

4. Optimal O(n)-space sweep

  • Initialize dp[0] from the start cell, then sweep every row updating the same array in place.
  • Obstacles reset their column to 0; open cells add the value to their left. The final answer is dp[cols-1].
def unique_paths_with_obstacles(obstacle_grid: list[list[int]]) -> int:
    cols = len(obstacle_grid[0])
    dp = [0] * cols
    dp[0] = 0 if obstacle_grid[0][0] == 1 else 1
    for row in obstacle_grid:
        for c in range(cols):
            if row[c] == 1:
                dp[c] = 0
            elif c > 0:
                dp[c] += dp[c - 1]
    return dp[cols - 1]

5. Dry run

Trace [[0,0,0],[0,1,0],[0,0,0]] with the rolling row.

after rowdp
row 0 [0,0,0][1,1,1]
row 1 [0,1,0][1,0,1]
row 2 [0,0,0][1,1,2]

The answer is dp[2] = 2.

6. Common mistakes and follow-ups

  • Seeding the start cell as 1 even when it is an obstacle, which over-counts every path.
  • Forgetting that an obstacle must reset its cell to 0 in the rolling array, not just skip it.
  • Assuming a blocked destination still has paths.
  • Follow-up: how would diagonal moves or a cost per cell change the recurrence?

7. Edge cases to test mentally

  • A single free cell has exactly one path; a single blocked cell has none.
  • A fully blocked row or column cuts every path to 0.
  • A blocked start or destination yields 0 regardless of the rest of the grid.

8. Final full solution and complexity

A row-by-row sweep over one rolling DP row counts obstacle-free paths. Time is O(m*n) and extra space is O(n).

def unique_paths_with_obstacles(obstacle_grid: list[list[int]]) -> int:
    cols = len(obstacle_grid[0])
    dp = [0] * cols
    dp[0] = 0 if obstacle_grid[0][0] == 1 else 1
    for row in obstacle_grid:
        for c in range(cols):
            if row[c] == 1:
                dp[c] = 0
            elif c > 0:
                dp[c] += dp[c - 1]
    return dp[cols - 1]

FAQ

See also

Practice Unique Paths II online (run code in the browser)Longest Increasing Path in a Matrix solution (hard)Best Time to Buy and Sell Stock solution (easy)Binary Tree Maximum Path Sum solution (hard)Cheapest Flights Within K Stops solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?