Cheapest Flights Within K Stops
Medium
💭 Introduction
You’re given n cities connected by flights. Each flight has a source city, destination city, and price. You need to find the cheapest price to fly from city src to city dst with at most K stops.
This is a constrained shortest path problem — we need the cheapest path, but with a limit on the number of intermediate stops.
Unlike standard shortest path problems, we can’t simply use Dijkstra’s algorithm because we have an additional constraint: the number of stops. This makes the problem more challenging and interesting!
🧩 Problem Statement
LeetCode #787 — Cheapest Flights Within K Stops
There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.
You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
🔍 Example 1:
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],
src = 0, dst = 3, k = 1
Output: 700
Explanation:
Graph:
0 --100--> 1 --600--> 3
| |
100 100
| |
v v
2 --------200-----> 3
Optimal path: 0 → 1 → 3 (cost = 700, 1 stop)
Alternative: 0 → 1 → 2 → 3 (cost = 400, but 2 stops > k=1)
🔍 Example 2:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]],
src = 0, dst = 2, k = 1
Output: 200
Explanation:
Graph:
0 --100--> 1 --100--> 2
| ^
+---------500---------+
Optimal path: 0 → 1 → 2 (cost = 200, 1 stop)
Direct path: 0 → 2 (cost = 500, 0 stops)
🔍 Example 3:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]],
src = 0, dst = 2, k = 0
Output: 500
Explanation:
With k=0 (no stops allowed), only direct flight: 0 → 2 (cost = 500)
🧠 Step 1: Understanding the Problem
Let’s break down what makes this problem unique:
Key Observations:
- Weighted directed graph: Flights have costs and directions
- Constraint on path length: At most K stops (K+1 edges)
- Not just shortest path: Need cheapest within constraint
- Trade-off: Cheaper path might require more stops
Why standard Dijkstra doesn’t work:
- Dijkstra finds absolute shortest path
- Doesn’t consider the stop constraint
- Might reject a path that’s longer but has fewer stops
The Challenge:
Cheaper path with more stops vs Expensive path with fewer stops
We need to track both cost AND number of stops!
🤔 Step 2: BFS Approach (Level-by-Level)
BFS naturally processes paths by number of stops:
from collections import deque, defaultdict
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]],
src: int, dst: int, k: int) -> int:
# Build adjacency list
graph = defaultdict(list)
for from_city, to_city, price in flights:
graph[from_city].append((to_city, price))
# BFS: (city, cost)
queue = deque([(src, 0)])
min_cost = float('inf')
# Track minimum cost to reach each city at each level
stops = 0
while queue and stops <= k:
size = len(queue)
for _ in range(size):
city, cost = queue.popleft()
# If we reached destination
if city == dst:
min_cost = min(min_cost, cost)
continue
# Explore neighbors
for next_city, price in graph[city]:
new_cost = cost + price
# Only continue if cost is reasonable
if new_cost < min_cost:
queue.append((next_city, new_cost))
stops += 1
return min_cost if min_cost != float('inf') else -1
Problem: This explores too many paths! We need pruning.
⏱️ Time Complexity: $O(n^k)$ - Exponential in worst case
🚀 Step 3: BFS with Pruning (Optimized)
Track the minimum cost to reach each city at each level:
from collections import deque, defaultdict
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]],
src: int, dst: int, k: int) -> int:
# Build graph
graph = defaultdict(list)
for from_city, to_city, price in flights:
graph[from_city].append((to_city, price))
# Track minimum cost to reach each city
min_cost_to_city = [float('inf')] * n
min_cost_to_city[src] = 0
# BFS: (city, cost)
queue = deque([(src, 0)])
stops = 0
while queue and stops <= k:
size = len(queue)
for _ in range(size):
city, cost = queue.popleft()
# Explore neighbors
for next_city, price in graph[city]:
new_cost = cost + price
# Only continue if we found a cheaper path
if new_cost < min_cost_to_city[next_city]:
min_cost_to_city[next_city] = new_cost
queue.append((next_city, new_cost))
stops += 1
return min_cost_to_city[dst] if min_cost_to_city[dst] != float('inf') else -1
⏱️ Time Complexity: $O(k \times E)$ where E = number of flights
📦 Space Complexity: $O(n + E)$
⚙️ Step 4: Modified Dijkstra with Stop Constraint
Use priority queue but track stops:
import heapq
from collections import defaultdict
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]],
src: int, dst: int, k: int) -> int:
# Build graph
graph = defaultdict(list)
for from_city, to_city, price in flights:
graph[from_city].append((to_city, price))
# Priority queue: (cost, city, stops)
pq = [(0, src, 0)]
# Track (city, stops) -> min_cost
visited = {}
while pq:
cost, city, stops = heapq.heappop(pq)
# If we reached destination
if city == dst:
return cost
# If we've used all stops
if stops > k:
continue
# Skip if we've visited this (city, stops) with lower cost
if (city, stops) in visited and visited[(city, stops)] <= cost:
continue
visited[(city, stops)] = cost
# Explore neighbors
for next_city, price in graph[city]:
new_cost = cost + price
new_stops = stops + 1
# Only add if we haven't found a better path
if (next_city, new_stops) not in visited or \
visited[(next_city, new_stops)] > new_cost:
heapq.heappush(pq, (new_cost, next_city, new_stops))
return -1
⏱️ Time Complexity: $O((n + E) \times k \log(n \times k))$
📦 Space Complexity: $O(n \times k)$
🧮 Step 5: Dynamic Programming Approach
Use DP where dp[i][j] = minimum cost to reach city j using at most i stops:
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]],
src: int, dst: int, k: int) -> int:
# dp[stops][city] = min cost to reach city with 'stops' stops
dp = [[float('inf')] * n for _ in range(k + 2)]
# Base case: 0 cost to reach source
for i in range(k + 2):
dp[i][src] = 0
# Fill DP table
for stops in range(1, k + 2):
for from_city, to_city, price in flights:
# Update cost to reach to_city
dp[stops][to_city] = min(
dp[stops][to_city],
dp[stops - 1][from_city] + price
)
# Find minimum cost with at most k stops
result = min(dp[stops][dst] for stops in range(k + 2))
return result if result != float('inf') else -1
⏱️ Time Complexity: $O(k \times E)$
📦 Space Complexity: $O(k \times n)$
🎯 Step 6: Space-Optimized DP
Only need previous and current row:
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]],
src: int, dst: int, k: int) -> int:
# Only need two rows: previous and current
prev = [float('inf')] * n
curr = [float('inf')] * n
prev[src] = 0
# Iterate k+1 times (k stops = k+1 edges)
for _ in range(k + 1):
curr = prev.copy() # Start with previous values
for from_city, to_city, price in flights:
curr[to_city] = min(curr[to_city], prev[from_city] + price)
prev = curr
return curr[dst] if curr[dst] != float('inf') else -1
⏱️ Time Complexity: $O(k \times E)$
📦 Space Complexity: $O(n)$ — Optimal!
🧪 Step 7: Complete Example Trace
Let’s trace through Example 1: n=4, flights=[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src=0, dst=3, k=1
Using DP approach:
| Stops | City 0 | City 1 | City 2 | City 3 | Flights Processed |
|---|---|---|---|---|---|
| 0 | 0 | ∞ | ∞ | ∞ | Initial |
| 1 | 0 | 100 | ∞ | ∞ | 0→1 (100) |
| 2 | 0 | 100 | 200 | 700 | 1→2 (100), 1→3 (600) |
Result: 700 (path: 0 → 1 → 3)
Note: Path 0 → 1 → 2 → 3 (cost 400) requires 2 stops, which exceeds k=1.
🎯 Key Insights
-
Constraint changes algorithm: Can’t use standard Dijkstra due to stop limit
-
Multiple approaches work: BFS, modified Dijkstra, and DP all viable
-
Trade-offs: BFS is simpler, DP is more efficient, Dijkstra is flexible
-
State definition: Need to track both cost and stops
-
Pruning is crucial: Without it, search space explodes
📊 Complexity Summary
| Approach | Time | Space | Notes |
|---|---|---|---|
| Naive BFS | $O(n^k)$ | $O(n)$ | Too slow |
| BFS with Pruning | $O(k \times E)$ | $O(n)$ | Good for small k |
| Modified Dijkstra | $O((n+E) \times k \log(nk))$ | $O(n \times k)$ | Flexible |
| DP (2D) | $O(k \times E)$ | $O(k \times n)$ | Clear logic |
| DP (Optimized) | $O(k \times E)$ | $O(n)$ | Best space |
Where n = number of cities, E = number of flights, k = max stops
🌟 Edge Cases to Consider
- No path exists: Return -1
- Direct flight: k=0, only direct flights allowed
- Source equals destination: Return 0
- k >= n-2: Effectively no constraint (can visit all cities)
- Multiple paths with same cost: Any is valid
- Cycles in graph: DP handles naturally
💡 Common Mistakes
- Using standard Dijkstra: Doesn’t respect stop constraint
- Not tracking stops: Loses the constraint information
- Wrong stop counting: k stops = k+1 edges
- Not pruning: Explores too many paths
- Off-by-one errors: Careful with k vs k+1
🧪 Test Cases
# Test Case 1: Standard case
n = 4
flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
src, dst, k = 0, 3, 1
# Expected: 700
# Test Case 2: Direct flight cheaper
n = 3
flights = [[0,1,100],[1,2,100],[0,2,500]]
src, dst, k = 0, 2, 0
# Expected: 500
# Test Case 3: No path
n = 3
flights = [[0,1,100]]
src, dst, k = 0, 2, 1
# Expected: -1
# Test Case 4: Multiple stops needed
n = 5
flights = [[0,1,5],[1,2,5],[2,3,5],[3,4,5]]
src, dst, k = 0, 4, 3
# Expected: 20
# Test Case 5: Source equals destination
n = 3
flights = [[0,1,100]]
src, dst, k = 0, 0, 0
# Expected: 0
🔍 Variations of This Problem
- Network Delay Time - No stop constraint, simpler
- Path with Maximum Probability - Maximize instead of minimize
- Minimum Cost to Reach City - Similar constraint problem
- Shortest Path with Alternating Colors - Additional constraints
💡 Related Problems
- Dijkstra’s Algorithm - Base algorithm
- Network Delay Time - Simpler version
- Bellman-Ford Algorithm - Handles negative weights
- Path with Maximum Probability - Similar structure
🏆 Why This Problem Matters
- Real-world application: Actual flight booking systems
- Constrained optimization: Common in many domains
- Algorithm adaptation: Shows how to modify standard algorithms
- Interview favorite: Tests multiple concepts
- Trade-off analysis: Cost vs constraint balance
🎓 Key Takeaways
- Constraints matter: Stop limit changes the algorithm choice
- Multiple solutions: BFS, Dijkstra, and DP all work
- State tracking: Need to track both cost and stops
- Pruning essential: Reduces search space significantly
- DP is elegant: Clean solution with good complexity
📝 Interview Tips
- Clarify constraints: Confirm k means stops, not edges
- Discuss approaches: Mention BFS, Dijkstra, and DP
- Start simple: Begin with BFS, optimize if needed
- Handle edge cases: No path, k=0, src=dst
- Explain trade-offs: Why each approach works
- Test thoroughly: Walk through a small example
🔧 Python Tips
# Building adjacency list
from collections import defaultdict
graph = defaultdict(list)
for u, v, w in flights:
graph[u].append((v, w))
# BFS with level tracking
from collections import deque
queue = deque([(src, 0)]) # (city, cost)
stops = 0
# Priority queue for Dijkstra
import heapq
pq = [(0, src, 0)] # (cost, city, stops)
# DP initialization
dp = [[float('inf')] * n for _ in range(k + 2)]
dp[0][src] = 0
# Space-optimized DP
prev = [float('inf')] * n
prev[src] = 0
🎯 Problem-Solving Pattern
This problem follows the Constrained Shortest Path pattern:
- Identify: Shortest path with additional constraint
- Choose approach: BFS for simplicity, DP for efficiency
- Track state: Both cost and constraint (stops)
- Prune aggressively: Avoid exploring invalid paths
- Handle edge cases: No path, boundary conditions
This pattern applies to many optimization problems with constraints!