Cheapest Flights Within K Stops: A Step-by-Step Interview Walkthrough

Cheapest Flights Within K Stops is a problem that looks like a routine shortest-path question, but it quietly adds a twist that breaks the standard tool. You want the cheapest route from one city to another — that's Dijkstra's territory — except there's a constraint: you can use at most k stops. That single constraint is enough to make plain Dijkstra give wrong answers, and the candidates who don't understand why will apply it confidently and fail. The candidates who recognize that the stop limit makes "number of edges used" part of the problem's state — and who know that Bellman-Ford naturally tracks shortest paths by edge count — adapt cleanly. The signal interviewers want is whether you can recognize when a familiar algorithm's assumptions are violated and reach for the right variant instead of forcing the wrong tool.

Shortest path under a hop or resource constraint is a real, recurring problem. Flight and transit booking systems find cheapest routes within a maximum number of connections. Network routing finds least-cost paths within a bounded number of hops (to limit latency or TTL). Logistics systems minimize shipping cost subject to a maximum number of transfers. Any time you're optimizing cost but also limited in how many intermediate steps you can take, you're solving exactly this constrained-shortest-path problem.

Problem Statement

You are given n cities labeled 0 to n - 1, and a list of flights where flights[i] = [from, to, price] is a directed flight from from to to costing price.

You're also given a source src, a destination dst, and an integer k — the maximum number of stops allowed.

Return the cheapest price from src to dst using at most k stops. If no such route exists, return -1.

Example: 

n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2.

With k = 0, the answer is 500 (only the direct flight is allowed).

With k = 1, the answer is 200 (the two-leg route 0→1→2, which uses one stop).

1. Clarify Requirements Before Jumping Into Code

Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that would change our approach.

Input: the number of cities, a list of directed weighted flights, a source, a destination, and a stop limit k.

Output: the cheapest total price within the stop limit, or -1 if unreachable.

Details to clarify:

• Are flights directed? Yes — a flight from → to doesn't imply the reverse.

• What exactly counts as a "stop"? A stop is an intermediate city, not an edge. A direct flight (0→2) has zero stops. A two-leg route (0→1→2) has one stop. So at most k stops means at most k + 1 flights (edges).

• Are prices non-negative? Yes.

• Do we return the cost or the actual route? Just the cost.

• Can src == dst? Edge case worth confirming — typically the answer would be 0.

The thing to flag is that the stop limit makes this not a plain shortest-path problem. In ordinary shortest path, we only care about cost; here, how many edges we used to arrive somewhere matters just as much as the cost of arriving. A cheap route that uses too many stops is invalid, and a slightly pricier route within the stop limit might be the right answer. That means "number of edges used so far" has to be part of how we think about the problem.

2. Identify the Category of the Question

A few signals jump out:

• We have a weighted directed graph and want a minimum-cost path.

• There's an extra constraint: a cap on the number of edges (stops).

• The constraint interacts with the cost — we can't optimize cost alone.

That combination — weighted shortest path with an edge-count constraint — places this in the constrained shortest path family. The presence of weights rules out plain BFS (which ignores cost), and the edge-count constraint complicates plain Dijkstra (which optimizes cost without regard to how many edges a path uses). The right tool, as we'll build toward, is Bellman-Ford with a limited number of rounds, because Bellman-Ford's structure naturally tracks shortest paths by number of edges — exactly the quantity the constraint cares about.

3. Brute Force Solution

Let's think about the naive approach to understand the problem. The most direct idea is to enumerate every possible route from src to dst, discard the ones that use more than k stops, and take the cheapest of what remains.

explore all paths from src:
    if path reaches dst using ≤ k stops:
        track the minimum cost
return the minimum, or -1 if none

The number of paths in a graph is exponential — routes can branch and wind in countless ways — so enumerating them all is infeasible. Even bounding paths to k + 1 edges, the count still explodes.

The brute force does surface the crucial insight, though. We're filtering paths by edge count (≤ k + 1 edges) while minimizing cost. Those two quantities — edges used and cost accumulated — both matter, and they pull in different directions. That tension is the whole problem: we need an algorithm that tracks cost and respects an edge-count budget. The brute force can't, but it tells us exactly what a smarter algorithm has to do.

4. Brainstorm More Solutions

Step 1: Try Dijkstra and see where it breaks

Our instinct for "cheapest path in a weighted graph" is Dijkstra, so let's test whether it works here and learn from how it fails.

Dijkstra works by always expanding the cheapest-reachable node and finalizing that nodes distance the first time it's reached. Once a node is settled, Dijkstra never reconsiders it, because no cheaper path can exist. That finalization is what makes Dijkstra fast.

But it's also exactly what breaks here. Consider a node X reachable two ways: a cheap route that takes many stops, and a pricier route that takes few stops. Dijkstra settles X using the cheap-but-long route and locks it in. But what if the cheap route to X burns through too many stops? The pricier-but-shorter route to X might have been the one that could still reach dst in time — but Dijkstra already discarded it.

So Dijkstra's core assumption — that a node's optimal cost is independent of how we got there — is violated. The number of stops used to reach a node is part of what makes a path useful, and Dijkstra throws that information away.

Step 2: Try BFS and see where it breaks

BFS feels promising for a different reason: it explores in layers, and layers correspond naturally to edge counts. Layer 1 is everything one flight away, layer 2 is everything two flights away, and so on — which maps perfectly onto stops.

But BFS has the opposite problem from Dijkstra: it tracks hops but ignores cost. BFS would tell us which cities are reachable within k stops, but not the cheapest way to reach them, because it treats all edges as equal. With flights of varying prices, that's useless for finding the minimum cost.

So we have two tools, each capturing half of what we need: Dijkstra handles cost but not the stop constraint; BFS handles the layered stop structure but not cost. We need something that does both — tracks cost while respecting an edge-count budget.

Step 3: Building an edge-count-aware algorithm from scratch

We've seen what we need: track cost (which BFS can't) while organizing those costs by how many edges each path uses (which Dijkstra throws away). Let's try to build this directly and see what falls out.

Start from what we know for certain: at the very beginning, before taking any flight, the only city we can reach is src, at cost 0. Every other city is unreachable — cost infinity. That's our "zero edges" picture.

We need to store that cost somewhere, so let's set up the one piece of bookkeeping we need: an array cost[], where cost[v] holds the cheapest price we've found so far to reach city v. We initialize it to reflect our "zero flights" picture — cost[src] = 0, and every other city set to infinity, meaning "no known way to reach it yet."

Now ask: what can we compute from there? Our tool is relaxation — we look at a single flight (u, v, price) and ask, "if I already know how to reach u, does flying u → v give me a cheaper way to reach v than I currently have?"

Concretely, if cost[u] + price < cost[v], then we've found a better route to v, so we update cost[v].

The procedure is to sweep over all the flights and relax each one. Note what this means: we don't carefully pick which flights to process or in what order — we just run through the entire flight list. Most flights will do nothing on this first sweep. A flight (u, v, price) can only improve anything if cost[u] is already known, and right now the only known city is src (everything else is still infinity). So although we mechanically process every flight, the only ones that actually cause an update are those departing from src — relaxing from any other city means adding to infinity, which improves nothing and is skipped.

So after one full sweep, what have we learned? Exactly the cheapest cost to reach each city using at most one flight — because the only routes that could possibly exist with one edge are single flights leaving src, and those are precisely the updates we made in cost[].

Now — what if we do the sweep again. This second pass builds on the first. Now the cities reachable in one flight have real costs, so sweeping all flights once more extends those by one additional flight — giving us the cheapest cost to reach each city using at most two flights.

This gives us a pattern: After i full sweeps over all the flights, cost[v] holds the cheapest cost to reach v using at most i flights.

That is exactly the quantity our constraint cares about. "At most k stops" means "at most k + 1 flights," so we sweep over all the flights k + 1 times, and then cost[dst] is our answer. Each sweep buys us permission to use one more edge — so capping the sweeps caps the stops, precisely and naturally.

This repeated-relaxation procedure is the well-known Bellman-Ford algorithm; the only twist is that we deliberately stop after k + 1 rounds instead of running it to completion. But notice we didn't need to recall it — we derived it by asking "how do I extend reach by one edge at a time?"

Step 4: A subtlety that makes or breaks the edge count

There's a trap hiding in "sweep over all the flights," and it's the detail interviewers love to probe. Let's surface it by thinking carefully about what one sweep is supposed to mean.

A single sweep should add exactly one edge of reach. For that to hold, every improvement we make during the sweep must build on costs from before this sweep started. But watch what happens if we're careless. Suppose during round i we relax flight (a, b) and lower cost[b], and then later in the same sweep we relax flight (b, c) using that freshly-lowered cost[b]. We've just chained two flights — a → b → c — inside a single round. That path uses two edges, but we only meant to add one. The round's "at most i edges" promise is broken, and stops sneak in beyond the budget.

The fix follows directly from the diagnosis: each round must read costs as they were at the end of the previous round, ignoring any changes made during the current round. So at the start of every sweep, take a snapshot of the current costs. Read your cost[u] values from that frozen snapshot, but write improvements into the live array. That way, no improvement made this round can feed another improvement in the same round, and each sweep adds exactly one edge — no more.

for each round:
    temp = copy of cost              # freeze last round's values
    for each flight (u, v, price):
        if temp[u] + price < cost[v]: # read from the frozen snapshot
            cost[v] = temp[u] + price  # write into the live array

Skip this snapshot, and the algorithm will sometimes find paths that use more stops than allowed — a bug that quietly passes the easy test cases and fails exactly when an extra, illegal stop would have found a cheaper route. The snapshot is what keeps the promise "at most i edges per i rounds" honest.

Step 5: Walk through the example

Let's trace flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2.

Initialize: cost = [0, ∞, ∞] (only the source is reachable at cost 0).

k = 0 (run k + 1 = 1 round):

• Snapshot temp = [0, ∞, ∞].

• Flight 0→1 (100): temp[0] + 100 = 100 < ∞, so cost[1] = 100.

• Flight 1→2 (100): temp[1] = ∞, can't relax.

• Flight 0→2 (500): temp[0] + 500 = 500 < ∞, so cost[2] = 500.

• After 1 round: cost = [0, 100, 500]. Answer cost[2] = 500. Correct — with 0 stops, only the direct flight works.

k = 1 (run k + 1 = 2 rounds):

• Round 1 (as above): cost = [0, 100, 500].

• Round 2: snapshot temp = [0, 100, 500].

  • Flight 0→1 (100): temp[0] + 100 = 100, not less than current cost[1] = 100. No change.

  • Flight 1→2 (100): temp[1] + 100 = 200 < cost[2] = 500, so cost[2] = 200.

  • Flight 0→2 (500): no improvement.

• After 2 rounds: cost = [0, 100, 200]. Answer cost[2] = 200. Correct — with one stop, the two-leg route 0→1→2 costs 200.

The round count directly controls how many stops are allowed, exactly as intended.

Step 6: Complexity

Let E be the number of flights and k the stop limit. Each round relaxes all E edges once, and we run k + 1 rounds. So the time is O(E × (k + 1)) = O(E × k). The snapshot copy each round is O(n), done k + 1 times, which is dominated by the edge relaxation.

Space is O(n) for the cost array plus O(n) for the per-round snapshot.

Remember the transferable framing: the cost is "(number of rounds) × (work per round)" = "(edge budget) × (all edges)." Because we cap the rounds at k + 1 instead of running the full n - 1 rounds of standard Bellman-Ford, we directly trade the stop constraint for a smaller number of rounds.

5. Discuss Trade-Offs Between Solutions

Approach	Time	Space	When I'd use it
Brute-force path enumeration	Exponential	High	Never — paths explode
Dijkstra	O(E log V)	O(V)	Fast, but ignores the stop constraint — gives wrong answers here
BFS with cost tracking	O(E × k)	O(V)	Respects stops but awkward to make correct with weights
Bellman-Ford, k + 1 rounds	O(E × k)	O(V)	My default — the round structure tracks edge count directly

The limited-round Bellman-Ford is the right answer. Dijkstra is the tempting trap; recognizing why it fails (it finalizes a node's cost without regard to stops used) is exactly what the problem tests. There's a Dijkstra variant that works — adding stop-count to the priority-queue state so a node can be revisited with a different stop count — but it's fiddlier to get right, and Bellman-Ford's round structure expresses the constraint more naturally. I'd lead with Bellman-Ford and mention the modified-Dijkstra option if asked.

6. Pseudocode

cost[] = infinity for all cities
cost[src] = 0

repeat (k + 1) times:
    temp = copy of cost              # snapshot of previous round's values
    for each flight (u, v, price):
        if temp[u] is reachable and temp[u] + price < cost[v]:
            cost[v] = temp[u] + price
    # cost now reflects cheapest paths using one more edge than before

return cost[dst] if reachable, else -1

7. Edge Cases

Things to verify before claiming we're done:

• src == dst → cost[src] = 0 from the start; the answer is 0 (no flights needed).

• k = 0 → exactly one round; only direct flights are considered.

• No valid route within the stop limit → cost[dst] stays infinity → return -1.

• Multiple paths with different stop counts → the round count naturally restricts which paths are considered, picking the cheapest among the valid ones.

• k ≥ n - 1 → more rounds than needed; the result stabilizes to the true unconstrained shortest path (extra rounds change nothing, since no shortest path uses more than n - 1 edges).

The snapshot-per-round discipline is what makes the stop-count cases correct. Without it, a single round could chain multiple relaxations and admit paths with more stops than allowed.

8. Write Full Code

import java.util.*;

public class CheapestFlightsWithinKStops {

    public static int findCheapestPrice(
            int n,
            int[][] flights,
            int src,
            int dst,
            int k
    ) {
        int[] cost = new int[n];
        Arrays.fill(cost, Integer.MAX_VALUE);
        cost[src] = 0;

        // Run k + 1 rounds: at most k stops means at 
        // most k + 1 edges.
        for (int i = 0; i <= k; i++) {
            // Snapshot the previous round's costs. We READ from 
            // this copy and WRITE to `cost`, so each round adds 
            // exactly one edge of reach 
            int[] temp = Arrays.copyOf(cost, n);

            for (int[] flight : flights) {
                int u = flight[0];
                int v = flight[1];
                int price = flight[2];

                if (cost[u] != Integer.MAX_VALUE && cost[u] + price < temp[v]) {
                    temp[v] = cost[u] + price;
                }
            }

            cost = temp;
        }

        return cost[dst] == Integer.MAX_VALUE ? -1 : cost[dst];
    }
}

A note on this implementation: it reads from cost (the previous round) and writes to temp (the new round), then swaps cost = temp at the end of each round — which is the same snapshot discipline described in Step 4, just organized so the new array is the one being written. Either arrangement works as long as reads come from the previous round's values and each round adds exactly one edge.

9. Test the Code

int[][] flights = {
    {0, 1, 100},
    {1, 2, 100},
    {0, 2, 500}
};

System.out.println(findCheapestPrice(3, flights, 0, 2, 0));  // 500 (direct only)
System.out.println(findCheapestPrice(3, flights, 0, 2, 1));  // 200 (0→1→2, one stop)
System.out.println(findCheapestPrice(3, flights, 0, 2, 2));  // 200 (extra stop allowed, same best)

// No route within stop limit
int[][] f2 = {{0,1,100},{1,2,100},{2,3,100}};
System.out.println(findCheapestPrice(4, f2, 0, 3, 1));  // -1 (needs 2 stops, only 1 allowed)
System.out.println(findCheapestPrice(4, f2, 0, 3, 2));  // 300 (0→1→2→3, two stops)

// Source equals destination
System.out.println(findCheapestPrice(3, flights, 0, 0, 0));  // 0

// Cheaper-but-longer vs pricier-but-shorter
int[][] f3 = {{0,1,100},{1,2,100},{0,2,300}};
System.out.println(findCheapestPrice(3, f3, 0, 2, 0));  // 300 (must take direct — no stops)
System.out.println(findCheapestPrice(3, f3, 0, 2, 1));  // 200 (now the two-leg route wins)

These hit the meaningful cases: the canonical example at three stop limits, an unreachable-within-budget case (the -1), the source-equals-destination case, and the "cheaper-but-longer vs. pricier-but-shorter" tension that's the whole reason Dijkstra fails — at k = 0 we're forced onto the pricier direct flight, and only when stops are allowed does the cheaper multi-leg route become valid.

10. Key Lessons

• When a shortest-path problem adds a constraint (a stop limit, a hop cap, a resource budget), check whether your default algorithm's assumptions still hold. Dijkstra's "first arrival at a node is final" assumption breaks the moment the way you reached a node (how many stops it cost) affects whether you can continue. Recognizing the broken assumption is the whole problem.

• Bellman-Ford's round structure tracks shortest paths by number of edges. After i rounds, you have the cheapest paths using at most i edges. When a problem constrains the edge count, this maps perfectly — just cap the rounds.

• Snapshot state per round when an algorithm's correctness depends on not chaining updates within a single round. Reading from the previous round's values (not values updated mid-round) is what keeps the edge-count guarantee exact.

  
  

The thing that makes Cheapest Flights Within K Stops click is recognizing that the stop limit turns "number of edges used" into part of the problem's state, and that Bellman-Ford's round-by-round structure is built to track exactly that. Once you see that each round of Bellman-Ford corresponds to one more allowed edge, capping the rounds at k + 1 is the obvious, natural fit. Training yourself to ask "does this constraint break my default algorithm's assumptions?" is what keeps you from confidently applying Dijkstra where it doesn't belong.

Good Luck and Happy Coding!