A fare search is asked for the cheapest itinerary from src to dst with at most k stops. The intern copied Network Delay Time: Dijkstra from src, first pop of dst is the answer. Staging with a generous k matched. Production with k = 1 returned the three-hop fare of 400 while the two-hop of 700 sat unused — the cheap path used too many flights. They then DFS’d every remaining-hop walk. A dozen cities returned. A few hundred on a dense mesh were still walking when the request timed out.

Cheapest Flights Within K Stops asks for the cheapest price from src to dst using at most k + 1 flights, or -1 if no such itinerary exists. A graph of directed priced edges already gives neighbors for free. Walking every hop-bounded path uses that and still pays exponential branching.

This is an interview writeup, not a layout lecture. That post owns adjacency list versus matrix. Bellman-Ford owns relax every edge, V - 1 times. Dijkstra owns settle-the-closest. Here we only care about a hop budget: at most k stops is at most k + 1 edges, so k + 1 relax rounds and a snapshot so a same-round write does not leak an extra flight. Unconstrained Dijkstra is the Network Delay Time board; this prompt is not that prompt.

The problem

n cities labeled 0 through n - 1. flights[i] = [from, to, price] is a directed flight. Return the cheapest price from src to dst with at most k stops — equivalently, a path of at most k + 1 edges — or -1 if none exists.

n = 4, src = 0, dst = 3, k = 1
flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]  →  700

n = 3, src = 0, dst = 2, k = 1
flights = [[0,1,100],[1,2,100],[0,2,500]]                      →  200

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

n = 3, src = 0, dst = 2, k = 1
flights = [[0,1,100]]                                          →  -1

First row: 0 → 1 → 2 → 3 costs 400 but uses two stops; with k = 1 the legal walk is 0 → 1 → 3 at 700. Second: one stop through 1 beats the direct 500. Third: k = 0 is the direct flight only. Fourth: dst is unreachable in the budget.

Note: Plain Dijkstra without the stop in the state is wrong. First-pop-is-final is legal when every path is allowed, as in Network Delay Time. Here a cheaper path may use too many hops, and a costlier path with fewer stops can be the one that is allowed. Enumerating every hop-bounded walk from src is also correct — that is the honest brute, not the board.

DFS every remaining-hop walk is the honest brute force

Build a directed adjacency list. Recurse from src with k + 1 edges left. Hitting dst records the cost. Zero edges left and you are not there: give up. Each outgoing flight spends one edge. The hop budget is what terminates a cycle; you do not need a visited set. Correct. Exponential.

int findCheapestPriceDfs(int n, int[][] flights, int src, int dst, int k) {
    List<List<int[]>> adj = new ArrayList<>(n);
    for (int i = 0; i < n; i++) {
        adj.add(new ArrayList<>());
    }
    for (int[] f : flights) {
        adj.get(f[0]).add(new int[] { f[1], f[2] });
    }
    int[] best = { Integer.MAX_VALUE };
    dfs(src, dst, k + 1, 0, adj, best);
    return best[0] == Integer.MAX_VALUE ? -1 : best[0];
}

void dfs(int u, int dst, int edgesLeft, int cost, List<List<int[]>> adj, int[] best) {
    if (u == dst) {
        best[0] = Math.min(best[0], cost);
        return;
    }
    if (edgesLeft == 0) {
        return;
    }
    for (int[] e : adj.get(u)) {
        int v = e[0];
        int w = e[1];
        if (cost + w >= best[0]) {
            continue;
        }
        dfs(v, dst, edgesLeft - 1, cost + w, adj, best);
    }
}

At n = 12 this is a rounding error. On a dense mesh you paid every walk of length at most k + 1: did this itinerary still have a flight left?

Relax k+1 rounds from src, snapshot each round

dist[src] = 0, everyone else ∞. Then k + 1 rounds: copy dist into next, and for every flight u → v of price w, if dist[u] + w is cheaper, write next[v]. Read the snapshot; write the copy. After that many rounds a cheapest path of at most k + 1 edges has had a chance to propagate. Return dist[dst], or -1 if it is still ∞. You scan the flights array; you do not queue a frontier.

Walk the mixed-hop trap. k = 1, so two rounds. Direct 0 → 1 → 3 is 700. The three-edge 400 needs a round you do not get.

dist: 0=0  1=∞  2=∞  3=∞

round 1  (1 edge, 0 stops)  read dist, write next
  0→1  next[1]=100
  1→2  dist[1]=∞   skip
  2→0  skip
  1→3  skip
  2→3  skip
dist: 0=0  1=100  2=∞  3=∞

round 2  (2 edges, 1 stop)  last round
  0→1  100 vs 100  no
  1→2  next[2]=200
  2→0  dist[2]=∞   skip
  1→3  next[3]=700
  2→3  dist[2]=∞ in the snapshot   skip
dist: 0=0  1=100  2=200  3=700

dst = 700

In-place, one round can chain 0→1 then 1→2 then 2→3 and write 400 with three edges. The snapshot refuses that leak. The Java is that walk:

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++) {
        int[] next = Arrays.copyOf(dist, n);
        for (int[] f : flights) {
            int u = f[0];
            int v = f[1];
            int w = f[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < next[v]) {
                next[v] = dist[u] + w;
            }
        }
        dist = next;
    }
    return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}

Time is O((k + 1) m) — k + 1 scans of every flight. Space is O(n) for dist and the snapshot. n is the city count (0 .. n - 1); m is flights.length. No adjacency list, no heap, no ArrayDeque.

Note: Guard the add: dist[u] is a real cost before you write dist[u] + w. Integer.MAX_VALUE + w wraps. Relax in place and one round can spend more than one new edge. The loop is round <= k, not n - 1: Bellman-Ford still owns the unconstrained V - 1 story; this board stops early because the prompt gave a hop cap. java.util.Stack is the wrong type.

What interviewers usually poke next

  • Network Delay Time. No stop budget. Unconstrained Dijkstra is then the right bill, and first-pop-is-final holds on non-negative weights. This prompt is the constrained twin: the cheapest path may be illegal.
  • Dijkstra with the stop in the state. A PriorityQueue of (cost, node, hops) — Java’s default min-heap, not reverseOrder(). Do not settle a node forever; a costlier arrival with fewer hops can still win. The heap is a follow-up, not the default board.
  • k = 0. Only a direct src → dst flight. Zero rounds would leave everyone but src at ∞; you still run one round (k + 1 = 1).
  • src == dst. Already there at cost 0, even when k = 0 and flights is empty.
  • Negative prices. Then the heap’s first pop is no longer final even with hops in the state. Name Bellman-Ford and keep the snapshot; this prompt promised non-negative price.

You are done with this problem when you can say, out loud, why unconstrained Dijkstra is wrong here, why k stops is k + 1 edges, and why the snapshot exists.