Budget Layovers

TIP103 Unit 12 Session 2 (Click for link to problem statements)

Budget Layovers

There are n cities and a list of flights where [from, to, price] is a one-way flight. Starting at src, you want to reach dst using at most k stops in between.

Return the cheapest total price, or -1 if dst is unreachable within k stops.

def find_cheapest_price(n, flights, src, dst, k):
    pass

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 30-40 mins
• 🛠️ Topics: Graphs, Shortest Path, Bellman-Ford, Breadth-First Search (BFS)

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What does "at most k stops" mean in terms of flights taken?

  • A stop is an intermediate city between src and dst, so k stops allows at most k + 1 flights on the route.

• Are the flights bidirectional?

  • No. Each entry [from, to, price] is a one-way flight from from to to.

• Is the cheapest route always the one with the fewest flights?

  • No. A route with more layovers can be cheaper, which is why we cannot simply run an unconstrained shortest-path search and stop at the first arrival.

HAPPY CASE
Input: n = 4, flights = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]], src = 0, dst = 3, k = 1
Output: 700
Explanation: With at most 1 stop, the best route is 0 -> 1 -> 3, costing 100 + 600 = 700. The cheaper route 0 -> 1 -> 2 -> 3 needs 2 stops, so it is not allowed.

Input: n = 4, flights = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]], src = 0, dst = 3, k = 2
Output: 400
Explanation: With up to 2 stops, the route 0 -> 1 -> 2 -> 3 becomes legal and costs 100 + 100 + 200 = 400.

EDGE CASE
Input: n = 4, flights = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]], src = 0, dst = 3, k = 0
Output: -1
Explanation: With 0 stops we may only take a single direct flight, and there is no flight 0 -> 3, so the destination is unreachable.

Input: n = 2, flights = [[0, 1, 100]], src = 0, dst = 0, k = 3
Output: 0
Explanation: We are already at the destination, so the cheapest price is 0.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Constrained Shortest Path Problems, we can consider the following approaches:

• Bellman-Ford (limited relaxation): Relax every flight exactly k + 1 times; after round i, we know the cheapest price to each city using at most i flights.
• Level-by-Level BFS: Traverse the graph one flight-layer at a time, pruning paths that are already more expensive than a known price to the same city.
• Plain Dijkstra does NOT directly work: greedily locking in the cheapest price to a city can discard a pricier partial route that uses fewer stops and is the only one that can still legally reach dst.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Use a Bellman-Ford style relaxation, but cap it at k + 1 rounds since at most k stops means at most k + 1 flights. Keep an array prices where prices[city] is the cheapest cost found so far to reach that city. In each round, relax every flight against a snapshot of the previous round's prices so that a single round can only extend a route by one flight.

1) Initialize `prices` of length n to infinity, and set `prices[src] = 0`.
2) Repeat k + 1 times:
   a) Copy `prices` into `temp`.
   b) For each flight (u, v, cost):
      i) If `prices[u]` is not infinity and `prices[u] + cost < temp[v]`,
         update `temp[v] = prices[u] + cost`.
   c) Replace `prices` with `temp`.
3) If `prices[dst]` is still infinity, return -1.
4) Otherwise, return `prices[dst]`.

⚠️ Common Mistakes

• Relaxing flights against the live prices array instead of a snapshot, which lets a single round chain multiple flights together and effectively ignores the k-stop limit.
• Looping only k times instead of k + 1 times — k stops permits k + 1 flights.
• Forgetting to return -1 when the destination is never reached.
• Trying plain Dijkstra and discarding more expensive partial routes that use fewer stops.

4: I-mplement

Implement the code to solve the algorithm.

def find_cheapest_price(n, flights, src, dst, k):
    INF = float('inf')
    # prices[i] = cheapest cost found so far to reach city i
    prices = [INF] * n
    prices[src] = 0

    # Relax every flight k + 1 times (k stops means at most k + 1 flights)
    for _ in range(k + 1):
        temp = prices[:]  # snapshot so each round adds at most one flight
        for u, v, cost in flights:
            if prices[u] != INF and prices[u] + cost < temp[v]:
                temp[v] = prices[u] + cost
        prices = temp

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

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: n = 4, flights = 0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200, src = 0, dst = 3, k = 1

  • Start: prices = [0, inf, inf, inf]
  • Round 1: relax from city 0 → prices = [0, 100, inf, inf]
  • Round 2: relax from city 1 → prices = [0, 100, 200, 700]
  • After k + 1 = 2 rounds, prices[3] = 700.
  • Output: 700

• Input: same flights, src = 0, dst = 3, k = 2

  • Round 1: prices = [0, 100, inf, inf]
  • Round 2: prices = [0, 100, 200, 700]
  • Round 3: city 2 now reaches city 3 for 200 + 200 = 400, which beats 700 → prices = [0, 100, 200, 400]
  • Output: 400

• Input: same flights, src = 0, dst = 3, k = 0

  • Only 1 round runs and no direct flight 0 -> 3 exists, so prices[3] stays infinity.
  • Output: -1

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of cities, E is the number of flights, and K is the maximum number of stops allowed.

• Time Complexity: O(K * E) because we perform K + 1 rounds and each round relaxes all E flights (copying the prices array adds O(K * N)).
• Space Complexity: O(N) for the prices array and its per-round snapshot.