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. Consider the following snippet from the optimal Zuma Game solution. Given board = "WRRBBW" and hand = "RB", what is the return value of findMinStep(board, hand)?

easy

A. 2

B. -1

C. 3

D. 1

Solution

1. Step 1: Trace initial calls with board="WRRBBW" and hand="RB"

   Hand has 1 R and 1 B. The board requires more balls to clear groups of 3, but hand is insufficient to clear all.

2. Step 2: Check if any insertion sequence clears board

   Trying to insert R or B balls to form groups of 3 fails due to insufficient balls; no sequence clears the board fully.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Return -1 indicates no solution with given hand [OK]

Hint: Insufficient hand balls cause no solution -> -1 [OK]

Common Mistakes:

• Assuming partial removals suffice to clear board
• Miscounting balls needed for group removal
• Forgetting to restore hand counts after recursion

2. What is the time complexity of the space-optimized bottom-up DP solution for the Maximal Square problem on an m x n matrix, and why might some candidates incorrectly think it is higher?

medium

A. O(m^3) because checking all squares requires nested loops

B. O(m * n * min(m,n)) because of checking all possible square sizes

C. O(m * n) because each cell is processed once with constant time updates

D. O(m + n) because only rows and columns are iterated separately

Solution

1. Step 1: Identify loops in the code

   Two nested loops iterate over rows and columns, each cell processed once.

2. Step 2: Understand DP update cost

   Each dp update is O(1), no nested checks for squares inside loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP avoids checking all squares explicitly [OK]

Hint: DP processes each cell once with constant work [OK]

Common Mistakes:

• Confusing brute force with DP complexity
• Assuming nested loops check all squares
• Ignoring constant time DP updates

3. The following code attempts to solve the Stone Game problem using bottom-up DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def stoneGame(piles):
    n = len(piles)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = piles[i]
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(piles[i] + dp[i+1][j], piles[j] + dp[i][j-1])
    return dp[0][n-1] > 0

medium

A. Line computing dp[i][j] = max(piles[i] + dp[i+1][j], piles[j] + dp[i][j-1])

B. Line initializing dp[i][i] = piles[i]

C. Line defining the outer loop for length in range(2, n+1)

D. Line returning dp[0][n-1] > 0

Solution

1. Step 1: Understand dp state meaning

   dp[i][j] should represent the maximum difference in stones the current player can achieve over the opponent.

2. Step 2: Identify incorrect recurrence

   The buggy line adds piles[i] + dp[i+1][j], which ignores the opponent's optimal response. The correct formula subtracts dp[i+1][j] to account for opponent's best play.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct recurrence uses subtraction, not addition [OK]

Hint: DP recurrence must subtract opponent's score [OK]

Common Mistakes:

• Adding dp values instead of subtracting opponent's score
• Forgetting base case initialization

4. Suppose the Burst Balloons problem is modified so that each balloon can be burst multiple times (reused), and bursting a balloon again yields coins based on the current adjacent balloons. Which of the following changes to the bottom-up DP approach correctly adapts to this variant?

hard

A. Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts

B. Modify the DP to consider only the first burst of each balloon and ignore reuse

C. Use the same interval DP but allow k to be chosen multiple times per interval

D. Use a greedy approach bursting the balloon with the maximum product of neighbors repeatedly

Solution

1. Step 1: Understand reuse impact

   Allowing multiple bursts per balloon means the problem state must track how many times each balloon has been burst, increasing complexity.

2. Step 2: Adapt DP state

   Interval DP assuming each balloon bursts once no longer works. We need a DP or memoization that tracks burst counts per balloon to correctly compute coins.

3. Step 3: Evaluate options

   Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts correctly proposes a stateful DP with counts and memoization. Use the same interval DP but allow k to be chosen multiple times per interval incorrectly reuses interval DP without state changes. Modify the DP to consider only the first burst of each balloon and ignore reuse ignores reuse, and D is greedy and incorrect.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking burst counts is necessary for reuse variants [OK]

Hint: Reuse requires tracking burst counts, not just intervals [OK]

Common Mistakes:

• Trying naive interval DP for reuse
• Ignoring state explosion
• Using greedy for complex DP variants

5. Suppose the Stone Game is modified so that players can pick stones from either end multiple times (i.e., reuse piles after picking). Which of the following changes correctly adapts the DP solution to handle this variant?

hard

A. Use a bottom-up DP with a sliding window over piles, but do not change the recurrence relation

B. Keep the same interval DP but add a loop to consider picking the same pile multiple times in one turn

C. Change dp state to represent maximum difference with unlimited picks and use a 1D dp array updated iteratively

D. Switch to a greedy approach since DP no longer applies when reuse is allowed

Solution

1. Step 1: Understand the impact of reuse

   Allowing reuse means piles are infinite or replenished, so intervals no longer shrink and the problem resembles unbounded knapsack.

2. Step 2: Adapt DP state and recurrence

   We need a 1D dp array representing maximum difference for each possible pile count, updated iteratively considering unlimited picks, similar to unbounded knapsack.

3. Step 3: Reject incorrect options

   Interval DP with multiple picks per turn or unchanged recurrence won't handle reuse correctly; greedy fails due to opponent's optimal play.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Reuse -> unbounded knapsack style DP with 1D array [OK]

Hint: Reuse -> unbounded knapsack DP, not interval DP [OK]

Common Mistakes:

• Trying to reuse interval DP unchanged
• Assuming greedy works with reuse