{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Cheapest Flights Within K Stops – Solution & Complexity

Interview solutions
/
Cheapest Flights Within K Stops

Solution Walkthrough

  1. Step 1: Bound the path length

    • At most k stops means at most k + 1 actual flight edges.
    • So you never need routes longer than k + 1 relaxations, even if the graph contains cycles.

  2. Step 2: Brute-force baseline

    • Explore all routes from src to dst with DFS while tracking how many stops remain.
    • That works for tiny graphs, but the branching factor makes it explode quickly.

  3. Step 3: Layered Bellman-Ford relaxation

    • Let prices[v] mean the cheapest known cost to reach city v using at most the previous number of edges.
    • On each of k + 1 rounds, copy the current array and relax every directed flight into the copy. Using the copy is crucial: it prevents one round from chaining together more than one new edge.
    • After k + 1 rounds, prices[dst] is the best cost using at most k + 1 edges, exactly matching the stop limit.

  4. Step 4: Final solution (all languages)

    A copied distance array per round enforces the stop budget while keeping the implementation compact.

    def find_cheapest_price(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
    prices = [float('inf')] * n
    prices[src] = 0

    for _ in range(k + 1):
        next_prices = prices[:]
        for start, end, price in flights:
            if prices[start] != float('inf') and prices[start] + price < next_prices[end]:
                next_prices[end] = prices[start] + price
        prices = next_prices

    return -1 if prices[dst] == float('inf') else prices[dst]

  5. Step 5: Why the copied array matters

    • If you relax into the same array you are reading from, one round might accidentally use two newly updated edges, violating the stop budget.
    • Using nextPrices guarantees round r only represents routes with at most r edges.
    • This is the same core Bellman-Ford idea, just stopped early because the interview problem limits the route length.

FAQ

See also

Practice Cheapest Flights Within K Stops online (run code in the browser)Longest Increasing Path in a Matrix solution (hard)Network Delay Time solution (medium)Word Ladder solution (hard)01 Matrix solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?