Cheapest Flights Within K Stops
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Find the cheapest price from src to dst using at most k stops (so at most k + 1 flights). Return -1 if impossible.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1How many flights does at most k stops allow?
- Hint 2Why must a round read from a copy of the previous costs?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Travel budgeting. A table shows the cheapest known price to reach each city using at most r flights. Round 1 starts from the home city with 0 and fills in the cities reachable by one flight. Round 2 uses the table from round 1 to find prices using two flights, and so on. After k + 1 rounds the table tells the cheapest price to the destination with at most k stops. You must read the previous round's table, not the one you are updating, so a round never sneaks in two flights.
- The obvious way
DFS trying all routes with at most k stops: exponential.
- The key insight
cost[city] starts as infinity except cost[src] = 0. Repeat k + 1 times: copy the costs; for every flight (from, to, price) if cost[from] is known and cost[from] + price is cheaper than the copy's cost[to], update the copy. Replace costs with the copy. Return cost[dst] or -1.
- The algorithm
- cost = infinity everywhere, 0 at src.
- Repeat k + 1 times: make a copy of cost.
- Relax every flight using the OLD costs, writing into the copy.
- Return cost[dst] (or -1 if infinity).
Watch it run
Exampleflights: 0>1 100, 1>2 100, 2>0 100, 1>3 600, 2>3 200; src 0, dst 3, k = 1
Before any flight: only city 0 is known, at price 0.
costs: 0, -, -, -
Where people slip
- k stops means k + 1 flights: loop k + 1 times.
- Relax from the OLD table; updating in place lets one round use many flights.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def find_cheapest_price(n, flights, src, dst, k):
infinity = float("inf")
cost = [infinity] * n
cost[src] = 0
for _ in range(k + 1): # at most k + 1 flights
today = cost[:] # read yesterday's table, write today's
for start, end, price in flights:
if cost[start] != infinity and cost[start] + price < today[end]:
today[end] = cost[start] + price
cost = today
return -1 if cost[dst] == infinity else cost[dst]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.