MediumDynamic ProgrammingDepth-First SearchBreadth-First SearchGraphHeapShortest PathUpdated Sep 2026

787. Cheapest Flights Within K Stops

Asked at TikTok, Flipkart

Difficulty

Medium

Time

O(k * E)

Space

O(n)

Pattern

Dynamic Programming

Companies

2

Problem

You are given n cities and a list of directed flights. Each flight is a triple [from, to, price], meaning you can fly from city from to city to for price dollars. You are also given a start city src, a target city dst, and an integer k.

Return the cheapest total price to travel from src to dst using at most k stops. A stop is an intermediate city you pass through. So k stops means the trip uses at most k + 1 flights. If no route exists within that limit, return -1.

The tricky part: the cheapest route by price may use too many stops. You must respect the stop limit, even if it forces you to pay more.

Cheapest route within the stop limit

0 → 1 : 1001 → 2 : 1002 → 3 : 200total 400, but 2 stops > k = 1This is the cheapest path, but it breaks the stoplimit.0 → 1 : 1001 → 3 : 600total 700, 1 stop = kThis path is more expensive but it fits inside thelimit, so it is the answer.
The cheap route 0 → 1 → 2 → 3 costs 400 but uses 2 stops, so with k = 1 we must take 0 → 1 → 3 for 700.

Constraints

  • ●2 <= n <= 100
  • ●0 <= flights.length <= n * (n - 1) / 2
  • ●flights[i].length == 3
  • ●0 <= from_i, to_i < n
  • ●from_i != to_i
  • ●1 <= price_i <= 10^4
  • ●There are no duplicate flights between the same pair of cities.
  • ●0 <= src, dst, k < n

Examples

Example 1
Inputn = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output700
WhyWith at most 1 stop, the only valid routes are 0 → 1 → 3 (cost 100 + 600 = 700) and 0 → 1 → 2 → 3, but that second one uses 2 stops, so it is not allowed. The answer is 700.
Example 2
Inputn = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output200
WhyThe route 0 → 1 → 2 uses exactly 1 stop and costs 100 + 100 = 200. The direct flight 0 → 2 costs 500, so 200 is cheaper and still within the limit.
Example 3
Inputn = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output500
WhyWith 0 stops you must fly directly. The only direct flight is 0 → 2 for 500, so the answer is 500.

Asked At

2 companies
CompanyDifficulty
TikTokMediumView all TikTok questions →
FlipkartMediumView all Flipkart questions →

How to Think About It

1

At most k stops means at most k + 1 flights (edges). The constraint is on the number of edges, not just the total cost.

2

Why plain Dijkstra fails: it finalizes the cheapest route to each city, but that route may already use too many stops, while a slightly more expensive route with fewer stops could still reach the destination in time.

3

Key insight: Bellman-Ford naturally counts edges. After i rounds of relaxing every edge, dist[v] is the cheapest cost using at most i edges — so run exactly k + 1 rounds.

4

Relax from a snapshot of the previous round (prev), not the array you are updating. Otherwise one round could chain several edges and exceed the stop limit.

5

Walkthrough: flights 0->1 (100), 1->2 (100), 0->2 (500), k = 1. Round 1: dist[1] = 100, dist[2] = 500. Round 2: dist[2] = min(500, 100 + 100) = 200. Answer 200.

Optimal Approach

Step 1: dist = [inf] * n, dist[src] = 0.
Step 2: Repeat k + 1 times:
prev = copy(dist)
For each flight (u, v, w): if prev[u] + w < dist[v], set dist[v] = prev[u] + w.
Step 3: Return dist[dst], or -1 if it is still infinity.

Time: O(k * E). Space: O(n).

Bellman-Ford with a snapshot

dist after round 001230infinfinfStart: only the source is reachable, at cost 0.dist after round 101230100infinfOne flight allowed: 0 → 1 costs 100. City 3 is stillunreachable.dist after round 201230100200700Two flights allowed: 1 → 3 gives 100 + 600 = 700.Answer is 700.for each round: prev = copy(dist)if prev[u] + w < dist[v]: dist[v] = prev[u] + wrun k + 1 rounds
Each round allows one more flight. We relax from the previous round's distances so one round cannot chain extra edges.
ComplexityTime O(k * E)Space O(n)We relax every edge (E of them) once per round, and we run k + 1 rounds; the distance array holds one value per city.

What Trips People Up in Real Interviews

1

Running standard Dijkstra keyed only on cost. It can return a path with too many stops or miss a valid cheaper-in-stops path.

2

Relaxing edges in place during a round. Without the prev snapshot, one round can use several consecutive edges.

3

Off-by-one on the rounds: k stops means k + 1 edges, so k + 1 relaxation rounds.

4

Returning infinity instead of -1 when dst is unreachable.

Solution Code

O(k * E) time
def findCheapestPrice(n, flights, src, dst, k):
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0
    for _ in range(k + 1):
        prev = dist[:]
        for u, v, w in flights:
            if prev[u] + w < dist[v]:
                dist[v] = prev[u] + w
    return -1 if dist[dst] == INF else dist[dst]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Cheapest Flights Within K Stops problem?

Cheapest Flights Within K Stops asks for the lowest price from `src` to `dst` using at most `k` intermediate stops, given a list of directed flights with prices. Plain Dijkstra fails because the cheapest path might use too many stops, so you need a shortest-path algorithm that respects an edge-count limit.

How do you solve Cheapest Flights Within K Stops?

The optimal approach runs in O(k * E) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Cheapest Flights Within K Stops?

Cheapest Flights Within K Stops is asked at TikTok, Flipkart. It is a medium difficulty problem.

What are common mistakes on Cheapest Flights Within K Stops?
  • Running standard Dijkstra keyed only on cost. It can return a path with too many stops or miss a valid cheaper-in-stops path.
  • Relaxing edges in place during a round. Without the `prev` snapshot, one round can use several consecutive edges.
  • Off-by-one on the rounds: `k` stops means `k + 1` edges, so `k + 1` relaxation rounds.
  • Returning infinity instead of `-1` when `dst` is unreachable.