Cheapest Flights Within K Stops
Asked at TikTok, Flipkart
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| TikTok | Medium | View all TikTok questions → |
| Flipkart | Medium | View all Flipkart questions → |
How to Think About It
At most k stops means at most k + 1 flights (edges). The constraint is on the number of edges, not just the total cost.
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.
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.
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.
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).
What Trips People Up in Real Interviews
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.
Solution Code
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]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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.