Cheapest Flights Within K Stops

1. Problem & Core Objective

Given n cities, a list of flights [from, to, price], a src, a dst, and an integer k, return the cheapest price from src to dst using at most k stops. Return -1 if no such route exists.

n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
src = 0, dst = 3, k = 1   →  700      (0→1→3)
same with k = 2           →  400      (0→1→2→3 = 100+100+200)

Constraints: 1 <= n <= 100 · 0 <= flights.length <= n(n−1)/2 · 1 <= price <= 10^4 · 0 <= k < n

What's actually being tested: that the hop limit breaks Dijkstra's core invariant. Dijkstra finalises a node on its first pop; with a stop cap, a pricier route using fewer hops may still be needed later. Bellman-Ford fixes it by bounding the rounds rather than the costs — and the round count is exactly k + 1.

2. First-Principles Thought Process

Why Dijkstra alone is wrong

Dijkstra's correctness rests on: the first time a node is popped, its cost is final. That holds because costs only grow as paths extend.

With a hop limit, a cheaper route to a node may use too many hops to be legal for continuing onward. So a more expensive route with fewer hops must remain available — and a single "best cost per node" can't represent both.

Concretely: reaching city X for 100 in 3 hops and for 300 in 1 hop. If the budget allows only one more hop, the 300 route is the useful one, but Dijkstra would have discarded it.

The fix: count rounds, not costs

Bellman-Ford relaxes every edge, once per round. After round i, dist[v] is the cheapest route to v using at most i edges.

"At most k stops" means at most k + 1 flights — a stop is an intermediate city, so 1 stop is 2 flights. So run k + 1 rounds.

That's the whole algorithm: the round count directly encodes the constraint.

The critical detail: read from the previous round

Within a round, every relaxation must read the previous round's distances. If a relaxation reads a value written earlier in the same round, a path could use two edges in one round — silently exceeding the hop budget.

int[] next = dist.clone();                 // write here
for (int[] f : flights)
    next[f[1]] = Math.min(next[f[1]], dist[f[0]] + f[2]);   // read from dist
dist = next;

Forgetting the clone is the classic bug, and it fails silently — producing a cheaper answer that uses too many stops.

Why k + 1 and not k

k stops means k intermediate cities, so k + 1 edges. With k = 1, 0 → 1 → 3 uses one stop and two flights. Off-by-one here is the other common error.

3. Solution Paths

Approach 1 — DFS over all paths with a depth cap (brute force)

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    Map<Integer, List<int[]>> adj = new HashMap<>();
    for (int[] f : flights)
        adj.computeIfAbsent(f[0], x -> new ArrayList<>()).add(new int[]{f[1], f[2]});

    return dfs(adj, src, dst, k + 1, new HashSet<>());
}

private int dfs(Map<Integer, List<int[]>> adj, int at, int dst, int edgesLeft,
                Set<Integer> onPath) {
    if (at == dst) return 0;
    if (edgesLeft == 0) return Integer.MAX_VALUE;

    int best = Integer.MAX_VALUE;
    onPath.add(at);
    for (int[] f : adj.getOrDefault(at, List.of())) {
        if (onPath.contains(f[0])) continue;                  // avoid cycles
        int sub = dfs(adj, f[0], dst, edgesLeft - 1, onPath);
        if (sub != Integer.MAX_VALUE) best = Math.min(best, f[1] + sub);
    }
    onPath.remove(at);
    return best;
}

• Time O(n^k) · Space O(k)

Counter-questions on this approach

⭐ "Why is this exponential?"

It explores every path of length up to k + 1 independently. With branching factor up to n and depth k + 1, that's O(n^k) — at n = 100 and k = 99 it's unimaginable.

And it recomputes heavily: the cheapest route from city X with 3 hops remaining is calculated afresh for every way of arriving at X.

⭐ "Could memoisation fix it?"

Yes, and that's the bridge to the right answer. Memoise on (city, edgesLeft) — there are n × (k+1) such states, and each does O(edges from that city) work. That gives O(k · E), which is exactly Bellman-Ford's complexity.

So the DP and Bellman-Ford are the same computation, one top-down and one bottom-up. Worth saying, because it shows Bellman-Ford isn't an unrelated trick.

"Why the onPath cycle guard?"

Without it, a cycle like 0→1→2→0 could be traversed repeatedly. The depth cap does bound it, but the guard prunes obviously-useless revisits.

Note that with all-positive prices a cycle never helps, so excluding them costs nothing. With negative prices it would be wrong to exclude them — but then the problem changes entirely.

Approach 2 — Bellman-Ford, k + 1 rounds (optimal)

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

    for (int round = 0; round <= k; round++) {          // k+1 rounds = at most k+1 flights
        int[] next = dist.clone();                       // snapshot the PREVIOUS round

        for (int[] f : flights) {
            int from = f[0], to = f[1], price = f[2];
            if (dist[from] == Integer.MAX_VALUE) continue;      // unreached — skip
            next[to] = Math.min(next[to], dist[from] + price);  // read dist, write next
        }
        dist = next;
    }

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

Trace — n = 4, flights as above, src = 0, dst = 3, k = 1:

Two rounds (k + 1 = 2), answer dist[3] = 700 ✓

With k = 2 a third round runs. dist[2] is 200 after round 1 (via 0→1→2), so relaxing 2→3 gives min(700, 200 + 200) = 400 — the cheaper three-flight route becomes legal once the budget allows two stops.

That contrast is the whole problem: the same graph answers 700 at k = 1 and 400 at k = 2, so the hop budget genuinely changes which route is optimal.

• Time O(k · E) · Space O(n)

Counter-questions on this approach

⭐ "Why k + 1 rounds rather than k?"

A "stop" is an intermediate city, so k stops means k + 1 flights. With k = 1, the route 0 → 1 → 3 has one stop and two edges.

After round i, dist[v] holds the cheapest route using at most i + 1 edges. So k + 1 rounds gives at most k + 1 edges, which is exactly k stops.

Getting this off by one is the single most common error, and it fails quietly — returning the answer for k − 1 or k + 1 stops.

⭐ "Why clone dist each round? What breaks without it?"

Without the clone, a relaxation can read a value written earlier in the same round, letting a path use two edges in one round. The hop budget is then silently exceeded.

Concretely with k = 0 (direct flights only) and flights 0→1 then 1→2 in that order: relaxing in place would set dist[1] and then immediately use it to set dist[2], reporting a two-flight route as reachable with zero stops.

Reading from the snapshot guarantees each round adds exactly one edge. This is the detail that makes it a bounded-hop algorithm rather than plain Bellman-Ford.

⭐ "Why the dist[from] == MAX_VALUE guard?"

Because MAX_VALUE + price overflows to a large negative number, which would then look like an excellent price and corrupt everything downstream.

It's the same sentinel-arithmetic discipline as elsewhere: Integer.MAX_VALUE as infinity is safe only if you never add to it.

"How does this compare to Dijkstra with a hop count in the state?"

That also works: make the heap entries (cost, city, stopsUsed) and allow a city to be visited multiple times with different stop counts. It's O(E · k log(E · k)) — correct, but more machinery and a subtler termination argument.

Bellman-Ford is O(k · E) = 99 × 4950 ≈ 5 × 10^5 here, simpler, and the round count encodes the constraint directly. I'd write Bellman-Ford and mention the Dijkstra variant.

"Does the order of the flights array matter?"

Not with the clone — every relaxation reads the same snapshot, so the result is order-independent. Without the clone it would matter, which is another symptom of the same bug.

"What if src == dst?"

dist[src] = 0 and no relaxation lowers it, so the answer is 0. Correct — you're already there.

Comparison

4. Why the Optimal Wins

Plain Dijkstra is wrong, not slow — its finality invariant assumes a cheaper route is always preferable, which the hop limit breaks.

The DFS is correct but exponential, and memoising it on (city, hopsLeft) produces exactly Bellman-Ford's state space.

Bellman-Ford bounds the rounds instead of the costs, so the constraint is expressed structurally rather than checked. O(k · E) with an O(n) array.

The framing worth keeping:

A hop limit breaks Dijkstra, because a pricier short route can outlive a cheaper long one. Bellman-Ford bounds the ROUNDS instead — k + 1 of them, each reading the previous round's snapshot so exactly one edge is added per round.

5. Java Prerequisites

Bellman-Ford with a bounded round count

for (int round = 0; round <= k; round++) {
    int[] next = dist.clone();                       // read from dist, write to next
    for (int[] f : flights)
        if (dist[f[0]] != Integer.MAX_VALUE)
            next[f[1]] = Math.min(next[f[1]], dist[f[0]] + f[2]);
    dist = next;
}

int[].clone() is a shallow copy — fine for primitives, and O(n) per round.

Infinity discipline — guard before adding to Integer.MAX_VALUE, or it overflows negative.

Stops vs edges — k stops = k + 1 edges = k + 1 rounds.

6. Interview Communication Guide

Clarifying questions: Does k count intermediate stops or flights (stops — so k + 1 flights; confirm, it's the off-by-one)? Are prices positive (yes)? Can there be cycles (yes)? What if src == dst (0)? Multiple flights between the same pair (possible; relaxation handles it)?

The pitch

"The instinct is Dijkstra, and it's wrong here — worth explaining why.

Dijkstra finalises a node the first time it's popped, which is valid because costs only grow as paths extend. But with a stop limit, a cheaper route to a city might use too many hops to continue onward, so a pricier route with fewer hops must stay available. One best-cost-per-node can't represent both.

Bellman-Ford fixes it by bounding the rounds rather than the costs. Each round relaxes every edge once, and after round i, dist[v] is the cheapest route using at most i + 1 edges.

Since k stops means k + 1 flights — a stop is an intermediate city — I run k + 1 rounds. That off-by-one is the first thing I'd double-check.

The critical implementation detail: each round must read the previous round's distances. I clone the array, read from the old one, and write to the new one. Without that, a relaxation could read a value written earlier in the same round, letting a path use two edges in one round and silently exceeding the hop budget. With k = 0 and flights 0→1 then 1→2 in that order, relaxing in place would report a two-flight route as reachable with zero stops.

I also guard against relaxing from an unreached city, since Integer.MAX_VALUE + price overflows negative and would look like a bargain.

O(k · E) — about 5 × 10^5 at these limits — with O(n) space.

There's a Dijkstra variant that works: put the stop count in the heap state so a city can be visited at several hop counts. Also correct, but more machinery and a subtler termination argument."

Edge cases to volunteer:

Name the k = 0 case and the cheaper-but-too-long route. The first exposes a missing clone instantly; the second is precisely the scenario Dijkstra gets wrong.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the route, not just the price."

Track a parent[] per round — but since a city's best predecessor differs by round, you need parent[round][city], which is O(k · n) space. Then walk back from (k+1, dst). More bookkeeping than the cost alone.

⭐ "What if prices could be negative?"

Bellman-Ford still works for bounded hops — the round structure doesn't assume positivity. But a negative cycle would make the unbounded problem undefined; with a hop cap it stays well-defined, since you can only go around so many times. That's a nice property of the bounded version worth mentioning.

"What if k were unbounded?"

Then it's plain shortest path and Dijkstra becomes correct again, at O(E log V) — much better than Bellman-Ford's O(V · E). The hop limit is precisely what rules Dijkstra out.

"Find the cheapest route with at most k stops for every destination."

This already computes it — dist[] holds the answer for every city, not just dst. The single-destination framing hides that Bellman-Ford is inherently single-source-all-destinations.

"What if there were 10^5 cities and 10^6 flights?"

O(k · E) with k up to 10^5 would be 10^11 — infeasible. You'd need the Dijkstra-with-state variant, pruning aggressively on (city, stops) pairs already seen at a lower cost.

"What if each flight also had a duration and you wanted the fastest within a price budget?"

Two-dimensional optimisation — minimise time subject to a cost cap. That's a constrained shortest path, which is NP-hard in general; you'd use a Lagrangian relaxation or a DP over discretised budget levels.