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. You are given a connected undirected graph where each node contains a value and a list of its neighbors. The task is to create a deep copy of this graph such that the cloned graph has the same structure but no shared nodes with the original. Which algorithmic approach guarantees an optimal solution that handles cycles and multiple components correctly?

easy

A. Use a brute force DFS that recursively clones neighbors without tracking visited nodes.

B. Use BFS or DFS with a hash map to track visited nodes and clone each node exactly once.

C. Use a greedy approach that clones nodes only when their values are unique.

D. Use dynamic programming to store intermediate clone results indexed by node values.

Solution

1. Step 1: Understand the problem constraints

   The graph may contain cycles and multiple components, so naive recursion can cause infinite loops or duplicate clones.

2. Step 2: Identify the correct approach

   Using BFS or DFS with a hash map to track visited nodes ensures each node is cloned once, preventing infinite recursion and preserving graph structure.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Tracking visited nodes avoids infinite loops and duplicates [OK]

Hint: Track visited nodes to avoid infinite recursion [OK]

Common Mistakes:

• Not tracking visited nodes causes infinite recursion
• Using node values as keys fails with duplicate values

2. You are given a 2D grid representing an image where each cell has a color value. Starting from a given pixel, you want to change the color of all connected pixels (4-directionally) that have the same original color to a new color. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Sorting pixels by color and recoloring in order to minimize recoloring steps

B. Greedy approach that recolors pixels as soon as they are found without revisiting neighbors

C. Dynamic Programming to store intermediate recoloring states for each pixel

D. Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all connected pixels with the original color

Solution

1. Step 1: Understand the problem as a connectivity search

   The problem requires recoloring all pixels connected 4-directionally with the same original color starting from a given pixel.

2. Step 2: Identify the algorithm that explores connected components

   DFS or BFS are standard graph traversal algorithms that explore all nodes reachable from a start node, which fits this problem perfectly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DFS/BFS ensures all connected pixels are visited exactly once [OK]

Hint: Flood fill is a graph traversal problem [OK]

Common Mistakes:

• Thinking greedy recoloring works without full traversal
• Confusing with DP which is not suitable here

3. Consider the following code snippet implementing the optimal BFS approach for the Surrounded Regions problem. Given the input board:

board = [
  ['X', 'X', 'X', 'X'],
  ['X', 'O', 'O', 'X'],
  ['X', 'X', 'O', 'X'],
  ['X', 'O', 'X', 'X']
]

After the BFS marking completes, what is the value of board[3][1]?

easy

A. 'O'

B. 'X'

C. 'S'

D. IndexError (out of bounds)

Solution

1. Step 1: Identify boundary 'O's and mark them

   Only board[3][1] is a boundary 'O', so it is marked 'S' and added to the queue.

2. Step 2: BFS expands from (3,1) marking connected 'O's

   From (3,1), no adjacent 'O's inside the board are connected, so only (3,1) remains 'S'. After BFS, all 'S' revert to 'O'.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Boundary 'O' at (3,1) remains 'O' after processing [OK]

Hint: Boundary 'O's remain 'O' after BFS marking [OK]

Common Mistakes:

• Confusing 'S' with final 'O' or 'X' states.
• Forgetting to revert 'S' back to 'O' after BFS.
• Assuming all 'O's get flipped regardless of boundary connection.

4. Examine the following buggy code snippet for the optimal BFS approach. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line that sets dist[nr][nc] = dist[r][c] + 1 without checking if dist[nr][nc] == -1

B. Line that initializes dist[r][c] = 0 for land cells

C. Line that appends initial land cells to the queue

D. Line that returns -1 if all cells are land or water

Solution

1. Step 1: Identify that updating dist[nr][nc] without checking if it was visited causes overwriting distances.

   This leads to revisiting cells multiple times, causing infinite loops or incorrect distances.

2. Step 2: The missing condition dist[nr][nc] == -1 before updating and enqueueing is the bug.

   Without it, BFS does not behave correctly as a shortest path search.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Visited check prevents infinite loops and ensures correct distances [OK]

Hint: Always check if neighbor is unvisited before updating distance [OK]

Common Mistakes:

• Forgetting visited check causes infinite loops
• Misplacing initialization lines
• Incorrect early return conditions

5. What is the time complexity of the optimal Dijkstra's algorithm variant solution for the minimum effort path problem on an n x m grid?

medium

A. O(n * m^2)

B. O(n * m * log(n * m))

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

D. O(n * m)

Solution

1. Step 1: Identify graph size

   The grid has n*m nodes and up to 4 edges per node, so edges E = O(n*m).

2. Step 2: Analyze Dijkstra's complexity

   Using a min-heap, each node is pushed/popped at most once, heap operations cost O(log(n*m)), total O(n*m*log(n*m)).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Log factor comes from heap operations on n*m nodes [OK]

Hint: Dijkstra on grid -> O(V log V) with V=n*m [OK]

Common Mistakes:

• Confusing edges with nodes count
• Assuming O(n*m^2) due to nested loops
• Ignoring log factor from heap