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

Unique Paths II – Solution & Complexity

Interview solutions
/
Unique Paths II

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 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. Step 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. Step 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. Step 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)Maximal Square solution (medium)01 Matrix solution (medium)Best Time to Buy and Sell Stock solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?