Cheapest Flights Within K Stops

PracticeNeetCode ↗LeetCode ↗

Given n cities connected by flights with prices, find the cheapest price from src to dst using at most k stops along the way. Return -1 if no such route exists.

Example

Key Pointers

• Plain Dijkstra doesn't track how many edges were used to reach a node, so it can't respect a stop limit on its own — Bellman-Ford's round count maps naturally onto "at most k+1 flights".
• Copy the distances array at the start of each round and relax edges against the previous round's values — that stops a single round from chaining more than one new flight per city.
• Run exactly k + 1 rounds of relaxation, since k stops means k + 1 flights.

Step-by-Step Analysis

1. Initialize a distances array of size n with infinity, except distances[src] = 0.
2. Repeat k + 1 times: copy the current distances into a temporary array.
3. For each flight (u, v, price), if distances[u] + price is cheaper than the temporary array's current value at v, update the temporary array.
4. Replace distances with the temporary array after each full round.
5. Return distances[dst] if it's still finite after all rounds, otherwise -1.

Complexity

Time: O(k · E) — Space: O(n)

Code

def findCheapestPrice(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
    distances = [float("inf")] * n
    distances[src] = 0

    for _ in range(k + 1):
        updated = distances.copy()
        for u, v, price in flights:
            if distances[u] != float("inf") and distances[u] + price < updated[v]:
                updated[v] = distances[u] + price
        distances = updated

    return distances[dst] if distances[dst] != float("inf") else -1

Code Explanation

How the solution above works, piece by piece.

1. distances[v] = cheapest known price from src to v; only src starts at 0.
2. Run k + 1 rounds, because k stops means at most k + 1 flights.
3. Each round relaxes every flight u → v, but reads from the previous round's array and writes into updated. Without the copy, one round could use several flights in a row and break the stop limit.
4. After the rounds, distances[dst] is the best price with at most k stops, or −1 if unreachable.
5. O(k · E) time, O(n) space.

Visual Walkthrough

Running it on the example with src = 0, dst = 3, k = 1:

Video Explanation

NeetCode — Bellman-Ford, Cheapest Flights Within K Stops, LeetCode 787