Cheapest Flights Within K Stops

▶

Steps

setup

Initialize cost arrays

Initialize the 'prev' cost array with infinity for all cities except the source city 0, which is set to 0. This represents the cost to reach each city with 0 stops.

💡 Setting the source cost to zero establishes the base case for DP; all other cities are initially unreachable.

Line:

INF = float('inf')
prev = [INF] * n
prev[src] = 0

💡 The algorithm starts with known cost 0 at source and unknown costs elsewhere.

expand

Start iteration 1 (up to 1 stop)

Begin the first iteration where we allow up to 1 stop. Copy 'prev' to 'curr' to start relaxing edges based on previous costs.

💡 Copying prev to curr preserves previous iteration costs before relaxation updates.

Line:

for _ in range(K + 1):
    curr = prev[:]

💡 We prepare a fresh cost array for this iteration to update with relaxed edges.

relax

Relax edge 0 -> 1

Check if city 0 is reachable (cost != ∞). Since prev[0] = 0, update curr[1] to min(curr[1], prev[0] + 100) = 100.

💡 Relaxing edges updates costs to reach neighbors if a cheaper path is found.

Line:

for u, v, w in flights:
    if prev[u] != INF:
        curr[v] = min(curr[v], prev[u] + w)

💡 Relaxation propagates known costs to neighbors, improving cost estimates.

relax

Relax edge 1 -> 2

Check if city 1 is reachable in prev. prev[1] is ∞, so no update to curr[2] is made from this edge.

💡 Only edges from reachable cities can relax costs to neighbors.

Line:

if prev[u] != INF:
    curr[v] = min(curr[v], prev[u] + w)

💡 Relaxation depends on previous iteration's reachable nodes.

relax

Relax edge 0 -> 2

Check if city 0 is reachable. prev[0] = 0, so update curr[2] to min(curr[2], prev[0] + 500) = 500.

💡 Relaxing direct flights from source updates costs even if longer than other paths.

Line:

if prev[u] != INF:
    curr[v] = min(curr[v], prev[u] + w)

💡 Direct flights provide initial cost estimates for destination city.

shrink

Finish iteration 1 and swap arrays

Finish relaxing all edges for iteration 1. Swap prev and curr so prev now holds updated costs for next iteration.

💡 Swapping arrays prepares for next iteration with updated costs.

Line:

prev = curr

💡 The DP state advances by one stop allowed, with updated minimum costs.

expand

Start iteration 2 (up to 2 stops)

Begin second iteration allowing up to 2 stops. Copy prev to curr to prepare for edge relaxations.

💡 Each iteration allows one more stop, expanding reachable paths.

Line:

for _ in range(K + 1):
    curr = prev[:]

💡 We prepare to find cheaper paths with one additional stop allowed.

relax

Relax edge 0 -> 1 again

Check if city 0 is reachable in prev (cost 0). Update curr[1] to min(curr[1], prev[0] + 100) = min(100, 0+100) = 100 (no change).

💡 Relaxation may not always improve costs but confirms current best.

Line:

if prev[u] != INF:
    curr[v] = min(curr[v], prev[u] + w)

💡 Relaxation maintains or improves costs, never worsens.

relax

Relax edge 1 -> 2 to improve cost

City 1 is reachable with cost 100 in prev. Update curr[2] to min(curr[2], prev[1] + 100) = min(500, 100 + 100) = 200.

💡 This relaxation finds a cheaper path to city 2 via city 1.

Line:

if prev[u] != INF:
    curr[v] = min(curr[v], prev[u] + w)

💡 Relaxation can improve costs by considering intermediate stops.

relax

Relax edge 0 -> 2 again

City 0 is reachable with cost 0. Update curr[2] to min(curr[2], prev[0] + 500) = min(200, 0 + 500) = 200 (no change).

💡 Relaxation confirms the cheaper path found via city 1 remains best.

Line:

if prev[u] != INF:
    curr[v] = min(curr[v], prev[u] + w)

💡 The algorithm keeps the minimum cost found so far.

shrink

Finish iteration 2 and swap arrays

Finish relaxing all edges for iteration 2. Swap prev and curr so prev now holds the final updated costs.

💡 Swapping arrays finalizes costs after allowing up to K stops.

Line:

prev = curr

💡 The DP arrays now contain the minimum costs with up to K stops.

reconstruct

Return final answer

Return the cost to reach destination city 2 from prev array. Since prev[2] = 200, return 200 as the cheapest price within K stops.

💡 The final DP array holds the answer after all relaxations.

Line:

return prev[dst] if prev[dst] != INF else -1

💡 The DP approach successfully finds the minimum cost path with constraints.

def findCheapestPrice(n, flights, src, dst, K):
    INF = float('inf')
    prev = [INF] * n  # STEP 1
    prev[src] = 0    # STEP 1
    for _ in range(K + 1):  # STEP 2
        curr = prev[:]      # STEP 2
        for u, v, w in flights:  # STEP 3-5,8-10
            if prev[u] != INF:
                curr[v] = min(curr[v], prev[u] + w)
        prev = curr          # STEP 6,11
    return prev[dst] if prev[dst] != INF else -1  # STEP 12

if __name__ == '__main__':
    n = 3
    flights = [[0,1,100],[1,2,100],[0,2,500]]
    src = 0
    dst = 2
    K = 1
    print(findCheapestPrice(n, flights, src, dst, K))  # Output: 200

📊

Cheapest Flights Within K Stops - Watch the Algorithm Execute, Step by Step

Watching each relaxation and update helps you understand how dynamic programming propagates minimum costs through the graph over iterations.

Visiting: none

0

1

2

Visiting: none

0

1

2

Visiting: 0

Edge: 0 → 1

0

1

2

Visiting: 1

Edge: 1 → 2

0

1

2

Visiting: 0

Edge: 0 → 2

0

1

2

Visiting: none

0

1

2

Visiting: none

0

1

2

Visiting: 0

Edge: 0 → 1

0

1

2

Visiting: 1

Edge: 1 → 2

0

1

2

Visiting: 0

Edge: 0 → 2

0

1

2

Visiting: none

0

1

2

Visiting: 2

0

1

2

Key Takeaways

✓ Dynamic programming propagates minimum costs through the graph by iteratively relaxing edges up to K+1 times.

This iterative relaxation is hard to visualize from code alone but becomes clear when watching each edge update step.

✓ The algorithm maintains two arrays to avoid using updated values within the same iteration, ensuring correctness.

Seeing the copy and swap of arrays clarifies why we don't update costs in place during relaxation.

✓ Relaxation only updates costs if the source city is reachable in the previous iteration, preventing invalid paths.

This conditional check is subtle in code but critical to understand how unreachable nodes don't affect costs.

Practice

1. Consider the following Python code implementing the space-optimized DP solution for counting unique paths with obstacles. Given the input grid below, what is the value of the dp array after processing the second row (i=1)? Input grid: [[0,0,0], [0,1,0], [0,0,0]]

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [0]*n
    dp[0] = 1 if obstacleGrid[0][0] == 0 else 0
    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 1:
                dp[j] = 0
            else:
                if j > 0:
                    dp[j] += dp[j-1]
    return dp[-1]

easy

A. [1, 1, 1]

B. [1, 1, 0]

C. [1, 0, 0]

D. [1, 0, 1]

Solution

1. Step 1: Initialize dp after first row (i=0)

   dp starts as [1,0,0]. After processing first row (all zeros), dp updates to [1,1,1].

2. Step 2: Process second row (i=1)

   At j=0, obstacleGrid[1][0]=0, dp[0] remains 1.
   At j=1, obstacleGrid[1][1]=1 (obstacle), dp[1] set to 0.
   At j=2, obstacleGrid[1][2]=0, dp[2] += dp[1] -> dp[2] = 1 + 0 = 1.
   Resulting dp: [1, 0, 1]

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   dp correctly zeroes obstacle cell and accumulates paths [OK]

Hint: Obstacles zero dp cells, dp[j] accumulates from dp[j-1] [OK]

Common Mistakes:

• Forgetting to zero dp[j] on obstacle
• Mis-updating dp[j] before dp[j-1]
• Confusing row and column indices

2. 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

3. The following code attempts to solve the Strange Printer problem using bottom-up DP. Which line contains a subtle bug that can cause incorrect results on inputs like "aba"?

medium

A. Line 18: dp[i][j] = dp[i][j - 1] + 1 assignment

B. Line 13: dp[i][i] = 1 initialization

C. Line 4: compressed.append(c) without checking for duplicates

D. Line 21: if s[k] == s[j] condition

Solution

1. Step 1: Identify compression step

   Line 4 appends every character without checking if it equals the last compressed character, so no compression occurs.

2. Step 2: Understand impact of missing compression

   Without compression, the DP runs on the full string length, causing inefficiency and possibly incorrect merges, especially on inputs like "aba" where compression reduces complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Compression step must skip duplicates to optimize DP [OK]

Hint: Compression must skip consecutive duplicates to avoid TLE and errors [OK]

Common Mistakes:

• Forgetting to compress string before DP

4. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the Unique Paths problem on an m x n grid?

medium

A. O(m^2 * n^2)

B. O(m + n)

C. O(m * n * min(m, n))

D. O(m * n)

Solution

1. Step 1: Identify loops in the code

   The solution uses two nested loops: outer loop runs m-1 times, inner loop runs n-1 times.

2. Step 2: Calculate total operations

   Total operations ≈ (m-1) * (n-1) -> O(m * n). No extra hidden loops or recursion stack.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested loops over m and n -> O(m*n) [OK]

Hint: Nested loops over m and n -> O(m*n) [OK]

Common Mistakes:

• Confusing with recursion exponential time
• Forgetting loops multiply complexity

5. Suppose the Strange Printer problem is modified so that the printer can reuse previously printed characters anywhere in the string without reprinting them. Which modification to the DP approach correctly handles this variant?

hard

A. Modify DP to consider non-contiguous intervals and allow merging non-adjacent segments

B. Add a global visited set to track printed characters and skip them

C. No change needed; original DP already accounts for reuse

D. Use a greedy approach printing each unique character once

Solution

1. Step 1: Understand reuse variant

   Reusing printed characters anywhere means intervals are no longer strictly contiguous; DP must consider merging non-adjacent segments.

2. Step 2: Identify correct DP modification

   Original DP assumes contiguous intervals. To handle reuse, DP must be extended to track sets of printed characters or allow merging non-contiguous intervals, which requires more complex state representation.

3. Step 3: Evaluate options

   No change (C) ignores new reuse property. Global visited set (B) is insufficient for interval merging. Greedy (D) fails on complex merges. Only (A) correctly adapts DP for non-contiguous merges.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Reuse breaks contiguous assumption; DP must handle non-adjacent merges [OK]

Hint: Reuse breaks contiguous intervals; DP must track complex merges [OK]

Common Mistakes:

• Assuming original DP handles reuse without changes
• Trying greedy approach