Cheapest Flights Within K Stops

There are n cities (0 .. n-1) connected by flights[i] = [from, to, price] (directed). Given src, dst, and k, return the cheapest price from src to dst using at most k stops (so at most k+1 flights), or -1 if there is no such route.

Hints

· Stuck? Reveal one nudge at a time.

At most k stops means at most k+1 flights — bound the number of edges.

Run Bellman-Ford for exactly k+1 rounds.

Relax each round off the previous round's distances (a copy) so one round adds only one flight.

Common doubts

Relaxing in place could chain several flights in a single round, exceeding the stop limit; a snapshot ensures each round extends paths by exactly one edge.

Dijkstra minimises cost ignoring hop count, so it may pick a cheaper route with too many stops. You must track edges used.

k stops equals k+1 flights (the stops are the intermediate cities).

Interview follow-ups

· What an interviewer asks next.

Use a priority queue keyed by cost with state (city, stops used), allowing revisits with more remaining stops.

Bellman-Ford still works for bounded edges, but a negative cycle would make 'cheapest' unbounded without the stop limit.

Fun facts

LeetCode 787 — the flagship 'shortest path with a hop constraint' problem.
The copy-per-round trick is the crux; relaxing in place is the classic bug here.

Asked at

AmazonGoogleMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
0→1→2 costs 200 with one stop, cheaper than the direct 500.

Example 2

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
With no stops, only the direct flight is allowed.

Constraints

- 1 <= n <= 100 - 0 <= flights.length <= n*(n-1) - 0 <= src, dst < n - 0 <= k < n - 1 <= price <= 10^4

The twist over plain shortest path is the stop limit: you can't just take the globally cheapest route if it uses too many flights. The clean handle is to bound the number of edges, not just minimise cost.

Bounded Bellman-Ford. A path with at most k stops has at most k+1 edges, and Bellman-Ford's i-th round settles all shortest paths using at most i edges. So run exactly k+1 rounds — but relax each round using the previous round's distances (a fresh copy), so a single round can't chain multiple edges. O(k·E).

Level BFS. Equivalently, BFS level by level from src, where each level adds one flight; stop after k+1 levels. Track the best cost to each city and only enqueue improvements. Same O(k·E) bound.

Prerequisites

Before you start

· Concepts used directly in the solution.

Edge-bounded relaxation. round i settles ≤ i-edge paths.

Copy per round. prevents chaining >1 edge in one round.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“k stops or k flights?”

k stops = k+1 flights.

“No valid route?”

Return -1.

The ideal opening — say it like this

At most k stops means at most k+1 edges, so I run Bellman-Ford for exactly k+1 rounds.

I relax each round off the previous round's distances so one round adds only one flight.

Understand the problem

Worked example — n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1

1 stop allowed: 0->1->2 = 200 (2 flights) beats the direct 0->2 = 500
answer = 200

Key observations

1Aha

k stops = k+1 edges

Bound the edge count, not just the cost.

2Aha

Round i settles ≤ i-edge paths

So k+1 rounds suffice.

3Aha

Relax off a snapshot

Copy distances each round to add one edge at a time.

Brute force vs optimal

	Bounded Bellman-Ford	Level BFS
Idea	k+1 rounds, relax off a copy	expand one flight per level, k+1 levels
Time	O(k·E)	O(k·E)
Edge bound	rounds	levels

Both respect the stop limit and give the same cheapest price. Full code is in the Approaches selector below.

Summary

Key takeaway

At most k stops = at most k+1 flights. Run Bellman-Ford for k+1 rounds, relaxing each round off the previous round's distances; or BFS level by level, k+1 levels. O(k·E).

for round in 0..k: tmp = copy(dist); relax all edges into tmp; dist = tmp
answer = dist[dst] or -1