Unique Paths II (With Obstacles)

▶

Steps

setup

Initialize dp array with zeros

Create a dp array of length equal to the number of columns (3), initialized with zeros.

💡 This array will store the number of unique paths to each cell in the current row.

Line:

dp = [0]*n

💡 The dp array represents the current state of path counts for each column.

setup

Set dp[0] based on start cell obstacle

Set dp[0] to 1 because the start cell (0,0) is not an obstacle.

💡 This means there is exactly one way to stand at the start cell.

Line:

dp[0] = 1 if obstacleGrid[0][0] == 0 else 0

💡 Starting point must be reachable to have any paths.

fill_cells

Process cell (0,0) - first row, first column

Check if cell (0,0) is an obstacle; it is not, so dp[0] remains 1.

💡 No obstacle means paths count stays as is.

Line:

if obstacleGrid[i][j] == 1:
    dp[j] = 0

💡 Obstacle check prevents counting paths through blocked cells.

fill_cells

Process cell (0,1) - first row, second column

Cell (0,1) is free, so update dp[1] by adding dp[0] (paths from left).

💡 Paths to this cell come from the left cell in the same row.

Line:

if j > 0:
    dp[j] += dp[j-1]

💡 Paths accumulate horizontally when no obstacle blocks.

fill_cells

Process cell (0,2) - first row, third column

Cell (0,2) is free, update dp[2] by adding dp[1].

💡 Paths flow from left to right in the first row.

Line:

if j > 0:
    dp[j] += dp[j-1]

💡 First row cells accumulate paths from left neighbors.

fill_cells

Process cell (1,0) - second row, first column

Cell (1,0) is free, no obstacle, dp[0] remains unchanged.

💡 First column dp values carry over from previous row if no obstacle.

Line:

if obstacleGrid[i][j] == 1:
    dp[j] = 0

💡 Paths can continue down the first column if no obstacle.

fill_cells

Process cell (1,1) - second row, second column (obstacle)

Cell (1,1) is an obstacle, so dp[1] is set to 0 to block paths.

💡 Obstacles reset path counts to zero at that position.

Line:

if obstacleGrid[i][j] == 1:
    dp[j] = 0

💡 No paths can pass through obstacles.

fill_cells

Process cell (1,2) - second row, third column

Cell (1,2) is free, update dp[2] by adding dp[1] (which is 0).

💡 Paths to this cell come from left and above, but left is blocked here.

Line:

if j > 0:
    dp[j] += dp[j-1]

💡 Paths can continue from above even if left is blocked.

fill_cells

Process cell (2,0) - third row, first column

Cell (2,0) is free, dp[0] remains unchanged (1).

💡 Paths continue down the first column if no obstacle.

Line:

if obstacleGrid[i][j] == 1:
    dp[j] = 0

💡 First column paths accumulate vertically.

fill_cells

Process cell (2,1) - third row, second column

Cell (2,1) is free, update dp[1] by adding dp[0].

💡 Paths come from left and above; dp[1] was 0, dp[0] is 1.

Line:

if j > 0:
    dp[j] += dp[j-1]

💡 Paths accumulate from left neighbor in current row.

fill_cells

Process cell (2,2) - third row, third column

Cell (2,2) is free, update dp[2] by adding dp[1].

💡 Paths come from left and above; dp[2] is 1, dp[1] is 1.

Line:

if j > 0:
    dp[j] += dp[j-1]

💡 Paths from left and above combine to total paths here.

reconstruct

Return final answer from dp array

Return dp[-1], which is dp[2] = 2, the number of unique paths avoiding obstacles.

💡 The last dp element holds the total paths to bottom-right corner.

Line:

return dp[-1]

💡 The dp array accumulates the answer in its last element after full iteration.

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [0]*n  # STEP 1: Initialize dp array
    dp[0] = 1 if obstacleGrid[0][0] == 0 else 0  # STEP 2: Set start cell
    for i in range(m):  # STEP 3: Iterate rows
        for j in range(n):  # STEP 4: Iterate columns
            if obstacleGrid[i][j] == 1:  # STEP 5: Obstacle check
                dp[j] = 0
            else:
                if j > 0:  # STEP 6: Update dp[j] from left
                    dp[j] += dp[j-1]
    return dp[-1]  # STEP 7: Return answer

if __name__ == '__main__':
    grid = [[0,0,0],[0,1,0],[0,0,0]]
    print(uniquePathsWithObstacles(grid))  # Output: 2

📊

Unique Paths II (With Obstacles) - Watch the Algorithm Execute, Step by Step

Watching each update to the dp array reveals how the algorithm accumulates path counts and handles obstacles, making the dynamic programming logic clear.

Item 0 - wt:0 val:0

i\w	0	1	2
i=0	0	0	0

Item 0 - wt:0 val:1

i\w	0	1	2
i=0	1	0	0

start cell

Item 0 - wt:0 val:1

i\w	0	1	2
i=0	1	0	0

free cell

Item 0 - wt:0 val:1

i\w	0	1	2
i=0	1	1	0

free cell

Item 0 - wt:0 val:1

i\w	0	1	2
i=0	1	1	1

free cell

Item 1 - wt:0 val:1

i\w	0	1	2
i=0	1	1	1

free cell

Item 1 - wt:0 val:0

i\w	0	1	2
i=0	1	0	1

obstacle

Item 1 - wt:0 val:1

i\w	0	1	2
i=0	1	0	1

free cell

Item 2 - wt:0 val:1

i\w	0	1	2
i=0	1	0	1

free cell

Item 2 - wt:0 val:1

i\w	0	1	2
i=0	1	1	1

free cell

Item 2 - wt:0 val:2

i\w	0	1	2
i=0	1	1	2

free cell

Item 2 - wt:0 val:2

i\w	0	1	2
i=0	1	1	2

answer cell

Key Takeaways

✓ The dp array accumulates the number of unique paths to each cell in the current row, updating in place.

This insight is hard to see from code alone because the dp array is reused and updated dynamically, which can be confusing without visualization.

✓ Obstacles reset dp values to zero, effectively blocking paths through those cells.

Seeing the dp array zeroed at obstacle positions visually clarifies how the algorithm excludes invalid paths.

✓ The final answer is stored in the last element of the dp array after processing all rows.

Understanding that the dp array's last element holds the total paths is easier when watching the final step highlight this cell.

Practice

1. What is the time complexity of the bottom-up dynamic programming solution for the Dungeon Game problem on an m x n grid, and why might some candidates mistakenly think it is higher?

medium

A. O(2^{m+n}) because all paths are explored recursively

B. O(m + n) since only one path is considered at a time

C. O(m * n * max(|dungeon[i][j]|)) due to health value range affecting computations

D. O(m * n) because each cell is computed once using constant time operations

Solution

1. Step 1: Identify loops

   The bottom-up DP uses nested loops over m rows and n columns, each cell computed once.

2. Step 2: Analyze per-cell work

   Each dp[i][j] calculation is O(1), involving min and max operations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP table size m*n and constant work per cell [OK]

Hint: DP fills m*n table once, no recursion overhead [OK]

Common Mistakes:

• Confusing brute force recursion with DP
• Thinking health values affect complexity

2. What is the time complexity of the bottom-up dynamic programming solution for the Stone Game problem with n piles, and why?

medium

A. O(n^3) because of three nested loops over the piles

B. O(n^2) because the DP table of size nxn is filled once with constant work per cell

C. O(2^n) because all subsets of piles are considered

D. O(n) because only linear passes over the piles are needed

Solution

1. Step 1: Identify loops in bottom-up DP

   There are two nested loops: one for length from 2 to n, and one for start index i, total O(n^2) iterations.

2. Step 2: Constant work per dp[i][j]

   Each dp[i][j] is computed with a constant number of operations (max of two values), so total time is O(n^2).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP table size nxn filled once with O(1) work per cell [OK]

Hint: Two nested loops over intervals -> O(n^2) [OK]

Common Mistakes:

• Confusing recursion stack space with time
• Assuming triple nested loops cause O(n^3)

3. What is the time complexity of the bottom-up DP solution for the Triangle minimum path sum problem with n rows, and why?

medium

A. O(n^2) because each element in the triangle is processed once

B. O(2^n) because of the exponential number of paths

C. O(n) because each row is processed once

D. O(n^3) because of nested loops over rows and columns

Solution

1. Step 1: Count total elements in triangle

   Triangle has 1 + 2 + ... + n = n(n+1)/2 elements, which is O(n^2).

2. Step 2: Analyze loops

   Outer loop runs n times, inner loop runs up to n times per iteration, total O(n^2) operations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each element processed once in nested loops [OK]

Hint: Sum of rows is O(n^2), so time is O(n^2) [OK]

Common Mistakes:

• Confusing number of rows with total elements
• Assuming exponential complexity due to recursion
• Overestimating complexity due to nested loops

4. Suppose the problem changes so that you can move down to the same column or adjacent columns multiple times, but you want to find the minimum falling path sum where you can reuse rows multiple times (i.e., you can revisit rows). Which modification to the bottom-up DP approach correctly handles this variant?

hard

A. Use the original DP but memoize results to avoid recomputation

B. Use the same bottom-up DP but allow cycles by iterating until no dp changes occur

C. Switch to a shortest path algorithm like Bellman-Ford on a graph representing allowed moves

D. Apply greedy approach picking minimum adjacent values repeatedly

Solution

1. Step 1: Understand the variant with row reuse

   Allowing revisiting rows means cycles in the path graph, which breaks the acyclic assumption of DP.

2. Step 2: Identify suitable algorithm

   Model the problem as a graph with edges representing allowed moves and use Bellman-Ford to find shortest paths with possible cycles.

3. Step 3: Why other options fail

   Bottom-up DP assumes acyclic progression; greedy ignores global optimality; memoization doesn't handle cycles properly.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Bellman-Ford handles negative cycles and repeated nodes [OK]

Hint: Cycles require graph shortest path algorithms, not DP [OK]

Common Mistakes:

• Trying to reuse DP without cycle handling
• Assuming memoization solves cycles

5. Suppose the triangle can contain negative numbers and you want to find the minimum path sum. Which modification to the bottom-up DP approach is necessary to correctly handle this variant?

hard

A. Add a check to reset dp values to zero if they become negative during updates

B. Use top-down DP with memoization to avoid incorrect overwrites caused by negative values

C. No modification needed; the existing bottom-up DP works for negative numbers as well

D. Use a breadth-first search to find the minimum path sum instead of DP

Solution

1. Step 1: Understand DP correctness with negative numbers

   Bottom-up DP computes minimum sums by combining current value with min of two below; negative values do not break this logic.

2. Step 2: Confirm no overwrite or invalid assumptions

   DP updates are independent of sign; no reset or BFS needed.

3. Step 3: Conclude no modification needed

   The existing bottom-up DP approach correctly handles negative numbers without changes.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   DP min operations handle negatives naturally [OK]

Hint: DP min works regardless of sign [OK]

Common Mistakes:

• Assuming negative numbers require resetting dp
• Thinking BFS is needed for negative weights
• Believing top-down memoization fixes negative value issues