Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Cheapest Flights Within K Stops
• Topics: Dynamic Programming, Depth-First Search, Breadth-First Search, Graph Theory, Heap (Priority Queue), Shortest Path

Problem gist

There are n cities, and each directed flight has a departure city, an arrival city, and a price. Given src, dst, and k, return the cheapest price from src to dst using at most k stops. If no such route exists, return -1.

The phrase “at most k stops” is the detail that controls the whole solution. A stop is an intermediate city, so a route with at most k stops can use at most k + 1 flights. The algorithm should optimize price while respecting that edge limit.

Best way to think about it

This is a shortest path problem with a limit on the number of edges. Plain Dijkstra is not enough if it stores only one best price per city, because a slightly more expensive route to a city may use fewer flights and leave room for a cheaper final route later.

The cleanest interview solution is a bounded Bellman-Ford dynamic program:

1. Let costs[city] mean the cheapest known price to reach city using the number of flights already processed.
2. Start with costs[src] = 0 and every other city unreachable.
3. Run exactly k + 1 relaxation rounds, because that is the maximum number of flights allowed.
4. In each round, relax every flight from the previous round’s costs into a copied array.

The copy is the key. It prevents one round from chaining multiple flights together. During round r, every update must represent a route using at most r flights, not an unlimited number of flights accidentally discovered inside the same loop.

Why this works

After the first relaxation round, the costs represent routes using at most one flight. After the second round, they represent routes using at most two flights. By induction, after k + 1 rounds, the destination cost is the cheapest route using at most k + 1 flights, which is exactly at most k stops.

Each round tries every flight, so any valid route of length r can be built by taking a valid route of length r - 1 to the flight’s departure city and then adding that final flight. Because every possible final flight is considered, the best valid price is not missed.

The time complexity is O((k + 1) * E), where E is the number of flights. The extra space is O(n) for the current and next cost arrays.

Python solution

from typing import List


class CheapestFlightSolver:
    """Find the cheapest route whose number of stops stays within the limit."""

    _UNREACHABLE_COST = 10**18

    def cheapest_price_with_stop_limit(
        self,
        city_count: int,
        flights: List[List[int]],
        source: int,
        destination: int,
        max_stops: int,
    ) -> int:
        max_flights = max_stops + 1
        cheapest_costs = [self._UNREACHABLE_COST] * city_count
        cheapest_costs[source] = 0

        for _ in range(max_flights):
            next_costs = cheapest_costs.copy()
            found_better_route = False

            for departure, arrival, price in flights:
                if cheapest_costs[departure] == self._UNREACHABLE_COST:
                    continue

                candidate_cost = cheapest_costs[departure] + price
                if candidate_cost < next_costs[arrival]:
                    next_costs[arrival] = candidate_cost
                    found_better_route = True

            cheapest_costs = next_costs

            # No city improved in this round, so extra allowed flights cannot help.
            if not found_better_route:
                break

        final_cost = cheapest_costs[destination]
        return -1 if final_cost == self._UNREACHABLE_COST else final_cost


class Solution:
    def findCheapestPrice(
        self,
        n: int,
        flights: List[List[int]],
        src: int,
        dst: int,
        k: int,
    ) -> int:
        solver = CheapestFlightSolver()
        return solver.cheapest_price_with_stop_limit(n, flights, src, dst, k)

Common traps

The most common mistake is updating the costs array in place during a relaxation round. That allows a route to take multiple flights in one round, so the algorithm can return a route that exceeds the stop limit.

Another common mistake is treating stops and flights as the same thing. If k = 0, the route must be direct, but it can still use one flight. That is why the loop runs k + 1 rounds.

A priority queue solution can also work, but its state must include both city and flights used. A single global “best cost per city” is not sufficient because reaching the same city with fewer flights can be more valuable than reaching it cheaply after using too many flights.

Interview follow-ups

How would you solve it with a priority queue?

Use a min-heap of (total_cost, city, flights_used) states. Pop the cheapest state first, and if it reaches dst, return its cost. When expanding a state, only add outgoing flights if flights_used < k + 1.

The important detail is that the visited or best-state tracking must include the number of flights used. A state for city x with one flight used is not equivalent to a state for city x with three flights used, because the first state has more remaining stop budget. A practical implementation can keep best[city][flights_used] and push a neighbor only when it improves that exact state.

This approach often performs well when the destination is found early, but the worst-case complexity can still be larger than the bounded Bellman-Ford version because the heap may hold several states for the same city at different depths.

What if the interviewer asks for the actual route, not just the price?

Extend the dynamic programming solution with predecessor tracking. Each time a relaxation improves next_costs[arrival], record that arrival came from departure during the current round. Because each round corresponds to a specific number of flights, the predecessor state should include both the city and the round.

After the final round, choose the best destination state among the allowed flight counts and walk the predecessor links backward to recover the route. This works for the same reason the price-only DP works: every improvement records the final flight of the best route for that exact edge budget.

The tradeoff is extra memory. The price-only solution needs O(n) space, while route reconstruction usually needs O((k + 1) * n) predecessor storage if the implementation wants clean backtracking.

What changes if the route must use exactly k stops?

Exactly k stops means exactly k + 1 flights. In that version, the algorithm should not keep “at most” costs by copying the old array forward as acceptable answers. Instead, each round should build costs for routes using exactly that many flights.

Initialize the source as reachable with zero flights, then compute a fresh next array on each round from the previous exact-flight array. After k + 1 rounds, return the destination cost from that exact round. This prevents shorter routes from being accepted when the interviewer explicitly requires the exact number of stops.

The complexity remains O((k + 1) * E) time. Space can stay O(n) if only the previous exact round and current exact round are needed.

What if flight prices could be negative?

The bounded Bellman-Ford dynamic programming solution still works because it does not rely on non-negative edge weights. It enumerates the best route under a fixed maximum number of flights, and there are only k + 1 relaxation rounds.

Dijkstra-style priority queue logic would no longer be reliable with negative prices, because popping the currently cheapest state does not guarantee that no cheaper route to the same state will appear later. For negative prices, the bounded DP is the safer interview answer.

Negative cycles are also less dangerous here than in unrestricted shortest path problems, because the stop limit caps the number of flights. A route can loop only while it still has remaining flight budget.

Takeaway

The problem becomes straightforward once the stop limit is translated into an edge limit. Use k + 1 Bellman-Ford rounds, copy the previous costs before relaxing flights, and the result is the cheapest route that stays inside the allowed number of stops.