#787 Cheapest Flights Within K Stops
the problem
In plain words
There are n cities and directed flights [from, to, price]. Find the cheapest price from src to dst using at most k stops (so at most k + 1 flights). Return -1 if impossible.
in n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
out 700
0→1→3 costs 700. 0→1→2→3 costs 400 but uses 2 stops.
in n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
out 200
in same, k = 0
out 500
No stops allowed → only the direct flight.
- 1 ≤ n ≤ 100
- 0 ≤ flights.length ≤ n·(n − 1)/2
- 1 ≤ price ≤ 10⁴
- No duplicate flights
- 0 ≤ src, dst, k < n, src ≠ dst
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBellman–FordDijkstra
Plain Dijkstra fails: the cheapest route to a middle city may use too many stops, and a pricier route with fewer stops gets thrown away. The extra dimension is the number of flights, and Bellman–Ford's rounds count exactly that.
solutions
From brute force to optimal
Level i = routes with exactly i flights. Expand k + 1 levels, keeping only cost improvements.
- frontier = {src: 0}, best[src] = 0.
- For each of k + 1 levels, extend every frontier city by one flight.
- Keep a route only if it beats best[v] (which already includes routes with fewer flights).
- Answer: best[dst] or -1.
k + 1 levels; each frontier has ≤ n cities and scans their edges once.
Adjacency list, best[] and two frontier maps.
class Solution { public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { List<List<int[]>> adj = new ArrayList<>(); 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 = new int[n]; Arrays.fill(best, Integer.MAX_VALUE); best[src] = 0; Map<Integer, Integer> frontier = new HashMap<>(); // node → cheapest cost at this level frontier.put(src, 0); // Level i of the BFS = routes that used exactly i flights. Allow at most k + 1. for (int flightsUsed = 0; flightsUsed <= k && !frontier.isEmpty(); flightsUsed++) { Map<Integer, Integer> nextLevel = new HashMap<>(); for (Map.Entry<Integer, Integer> cur : frontier.entrySet()) { for (int[] next : adj.get(cur.getKey())) { int v = next[0], cost = cur.getValue() + next[1]; // Keep it only if it beats every route with ≤ this many flights. if (cost < best[v]) { best[v] = cost; nextLevel.put(v, cost); } } } frontier = nextLevel; // at most n entries per level } return best[dst] == Integer.MAX_VALUE ? -1 : best[dst]; }}Make the flight count part of the state. Pop by cost; skip a city if an earlier (cheaper) pop already used fewer flights.
- Heap of {cost, city, flightsUsed}, start {0, src, 0}.
- Pop: if city = dst return cost. If flightsUsed = k + 1, skip.
- If flightsUsed ≥ the fewest flights seen for this city, skip (dominated).
- Push all neighbours with flightsUsed + 1.
Each (city, flights) state can push all its edges: up to k·E heap operations.
Heap entries for every state.
class Solution { public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { List<List<int[]>> adj = new ArrayList<>(); 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[] fewestFlights = new int[n]; // fewest flights seen when node was popped Arrays.fill(fewestFlights, Integer.MAX_VALUE); PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); pq.offer(new int[] {0, src, 0}); // {cost, node, flights used} while (!pq.isEmpty()) { int[] top = pq.poll(); int cost = top[0], u = top[1], used = top[2]; if (u == dst) return cost; // cheapest valid way to dst if (used == k + 1) continue; // no flights left if (used >= fewestFlights[u]) continue; // a cheaper pop already had fewer flights fewestFlights[u] = used; for (int[] next : adj.get(u)) pq.offer(new int[] {cost + next[1], next[0], used + 1}); } return -1; }}After round r, cost[v] = cheapest route with ≤ r flights. Run exactly k + 1 rounds, reading the previous round's array.
- cost[src] = 0, rest ∞.
- Repeat k + 1 times: next = cost.clone(); relax every flight from cost into next; cost = next.
- Answer cost[dst] or -1.
k + 1 rounds, each relaxing all E flights and copying the n-entry price array.
Two arrays of size n.
class Solution { public 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; for (int round = 1; round <= k + 1; round++) { int[] next = cost.clone(); // read old round, write new round for (int[] f : flights) { int u = f[0], v = f[1], price = f[2]; if (cost[u] != Integer.MAX_VALUE && cost[u] + price < next[v]) { next[v] = cost[u] + price; } } cost = next; } return cost[dst] == Integer.MAX_VALUE ? -1 : cost[dst]; }}Dry run
in the room
How to say it in the interview
talk track
- Clarify: k stops = k + 1 flights.
- Explain why plain Dijkstra is wrong with one small counter-example.
- Present Bellman–Ford with the copied array; stress that the copy is what enforces the limit.
traps
- Relaxing in place: in one round a route can chain 2+ flights, silently exceeding k.
- Off-by-one: the loop runs k + 1 times, not k.
what they ask next
Follow-ups
Also return the route?
Keep a parent per (city, round) — a 2D parent table — and walk back from (dst, k + 1).
What if k is huge (≥ n − 1)?
The limit no longer matters. Plain Dijkstra is then faster: O((n + E) log n).
before you submit
Edge cases to test
- k = 0 → only a direct flight counts.
- The cheapest route needs too many stops: 0→1→2→3 costs 3 with 2 stops, so with k = 1 the answer is the pricier 6.
- dst can't be reached at all → -1.
- Flights form a cycle (2 → 0): the round limit keeps it from looping.
practise next
Similar problems
- #743Network Delay TimeMediumin Shortest Paths
- #1976Number of Ways to Arrive at DestinationMediumin Shortest Paths
- #1091Shortest Path in Binary MatrixMediumin Graphs