Log inSign up
mediumLeetCodeNot Started

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.

Graph
Solve on LeetCode
Lesson

Problem Statement

### Problem Statement

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i, to_i, price_i] indicates that there is a flight from city from_i to city to_i with cost price_i.

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.

---

### Examples

Example 1: ``text 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: The optimal path with at most 1 stop from city 0 to 3 is 0 -> 1 -> 3 with cost 100 + 600 = 700. The path 0 -> 1 -> 2 -> 3 has cost 100 + 100 + 200 = 400, but it takes 2 stops, which exceeds k = 1.

Example 2: ``text Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 Output: 200 Explanation: The path 0 -> 1 -> 2 has cost 200 with 1 stop. The direct path 0 -> 2 has cost 500 with 0 stops. Minimum cost is 200.

Example 3: ``text 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 stops, we must take the direct flight 0 -> 2 with cost 500.

---

### Constraints - 1 <= 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 will not be any multiple flights between two cities in the same direction. - 0 <= src, dst, k < n - src != dst

Constraints:

  • 1 <= 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 <= 104
  • There will not be any multiple flights between two cities in the same direction
  • 0 <= src, dst, k < n
  • src != dst

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate hop-constrained shortest path problems.
  • Implement Bellman-Ford with strict iteration snapshotting to avoid intra-round chaining.
  • Compare BFS level-by-level relaxation with Dijkstra state-pruned queues.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Shortest path on a directed weighted graph
  • Explicit constraint on the maximum number of intermediate nodes / edges allowed
  • Finding cheapest route under hop budget

Algorithmic Decision Tree:

  • 1. If path length constraint k is small or fixed: Use Bellman-Ford with k + 1 iterations and previous snapshot.
  • 2. For each iteration 0 to k: temp = clone(dist). For each edge (u, v, w): if dist[u] != inf, temp[v] = min(temp[v], dist[u] + w). Then dist = temp.
  • 3. Return dist[dst] == inf ? -1 : dist[dst].

Connected Patterns:

Network Delay TimeDijkstra Shortest PathBellman Ford Algorithm

1. DFS / Backtracking with Pruning

Intuition

Explore all paths from src to dst using DFS with depth limit k + 1 and branch-and-bound pruning on current cost.

Algorithm

  1. Build adjacency list from flights.
  2. Maintain global minCost = infinity.
  3. Track visited set to avoid infinite cycles.
  4. Define dfs(curr, stops, cost):
  5. If cost >= minCost or stops > k + 1, return.
  6. If curr == dst, update minCost = min(minCost, cost), return.
  7. For each neighbor (nextCity, price) in adj[curr]:
  8. If not visited[nextCity]:
  9. visited[nextCity] = true.
  10. dfs(nextCity, stops + 1, cost + price).
  11. visited[nextCity] = false.
  12. Call dfs(src, 0, 0).
  13. Return minCost == infinity ? -1 : minCost.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <climits>
4#include <algorithm>
5
6class Solution {
7 void dfs(int curr, int dst, int k, int stops, int cost, int& minCost,
8 const std::vector<std::vector<std::pair<int, int>>>& adj,
9 std::vector<bool>& visited) {
10 if (cost >= minCost) return;
11 if (curr == dst) {
12 minCost = cost;
13 return;
14 }
15 if (stops > k) return;
16
17 visited[curr] = true;
18 for (const auto& [nextCity, price] : adj[curr]) {
19 if (!visited[nextCity]) {
20 dfs(nextCity, dst, k, stops + 1, cost + price, minCost, adj, visited);
21 }
22 }
23 visited[curr] = false;
24 }
25public:
26 int findCheapestPrice(int n, std::vector<std::vector<int>>& flights, int src, int dst, int k) {
27 std::vector<std::vector<std::pair<int, int>>> adj(n);
28 for (const auto& f : flights) {
29 adj[f[0]].push_back({f[1], f[2]});
30 }
31 std::vector<bool> visited(n, false);
32 int minCost = INT_MAX;
33 dfs(src, dst, k, 0, 0, minCost, adj, visited);
34 return minCost == INT_MAX ? -1 : minCost;
35 }
36};
37
38int main() {
39 Solution sol;
40 std::vector<std::vector<int>> flights = {{0,1,100},{1,2,100},{2,0,100},{1,3,600},{2,3,200}};
41 std::cout << "Cheapest price: " << sol.findCheapestPrice(4, flights, 0, 3, 1) << " (Expected: 700)\n";
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(V^(K + 1))
  • Space complexity: O(V)

2. BFS Level-by-Level Queue Relaxation

Intuition

Perform level-order BFS up to k + 1 levels. Maintain an array of minimum costs seen so far to prune suboptimal queue states.

Algorithm

  1. Initialize prices array of size n with infinity, and prices[src] = 0.
  2. Initialize queue with [src, 0].
  3. Set stops = 0.
  4. While queue is not empty and stops <= k:
  5. Get current queue size sz.
  6. Iterate sz times (process full level):
  7. Pop [city, currentCost].
  8. For each neighbor (nextCity, price) in adj[city]:
  9. If currentCost + price < prices[nextCity]:
  10. prices[nextCity] = currentCost + price.
  11. Push [nextCity, currentCost + price] to queue.
  12. Increment stops.
  13. Return prices[dst] == infinity ? -1 : prices[dst].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <climits>
5
6class Solution {
7public:
8 int findCheapestPrice(int n, std::vector<std::vector<int>>& flights, int src, int dst, int k) {
9 std::vector<std::vector<std::pair<int, int>>> adj(n);
10 for (const auto& f : flights) {
11 adj[f[0]].push_back({f[1], f[2]});
12 }
13
14 std::vector<int> minPrice(n, INT_MAX);
15 minPrice[src] = 0;
16
17 // Queue stores {city, currentCost}
18 std::queue<std::pair<int, int>> q;
19 q.push({src, 0});
20 int stops = 0;
21
22 while (!q.empty() && stops <= k) {
23 int sz = q.size();
24 for (int i = 0; i < sz; ++i) {
25 auto [city, cost] = q.front();
26 q.pop();
27
28 for (const auto& [nextCity, price] : adj[city]) {
29 if (cost + price < minPrice[nextCity]) {
30 minPrice[nextCity] = cost + price;
31 q.push({nextCity, cost + price});
32 }
33 }
34 }
35 stops++;
36 }
37
38 return minPrice[dst] == INT_MAX ? -1 : minPrice[dst];
39 }
40};
41
42int main() {
43 Solution sol;
44 std::vector<std::vector<int>> flights = {{0,1,100},{1,2,100},{2,0,100},{1,3,600},{2,3,200}};
45 std::cout << "BFS Cheapest: " << sol.findCheapestPrice(4, flights, 0, 3, 1) << " (Expected: 700)\n";
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(K * E)
  • Space complexity: O(V + E)

3. Bellman-Ford Algorithm with Snapshot Copy (Gold Standard)

Intuition

Run Bellman-Ford edge relaxation for exactly k + 1 iterations using a cloned snapshot of distance array to prevent multi-hop cascades.

Algorithm

  1. Initialize prices array of size n with infinity, and prices[src] = 0.
  2. Loop i from 0 to k (total k + 1 iterations):
  3. Create a snapshot copy: temp = clone(prices).
  4. For each flight [u, v, price] in flights:
  5. If prices[u] != infinity:
  6. If prices[u] + price < temp[v]:
  7. temp[v] = prices[u] + price.
  8. Set prices = temp.
  9. Return prices[dst] == infinity ? -1 : prices[dst].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <climits>
4#include <algorithm>
5
6class Solution {
7public:
8 int findCheapestPrice(int n, std::vector<std::vector<int>>& flights, int src, int dst, int k) {
9 std::vector<int> prices(n, 1e9);
10 prices[src] = 0;
11
12 // Exactly k + 1 iterations for at most k stops (k + 1 edges)
13 for (int i = 0; i <= k; ++i) {
14 std::vector<int> temp = prices; // Cloned snapshot
15
16 for (const auto& f : flights) {
17 int u = f[0], v = f[1], price = f[2];
18 if (prices[u] != 1e9) {
19 temp[v] = std::min(temp[v], prices[u] + price);
20 }
21 }
22
23 prices = temp;
24 }
25
26 return prices[dst] >= 1e9 ? -1 : prices[dst];
27 }
28};
29
30int main() {
31 Solution sol;
32 std::vector<std::vector<int>> flights = {{0,1,100},{1,2,100},{2,0,100},{1,3,600},{2,3,200}};
33 std::cout << "Optimal Bellman-Ford: " << sol.findCheapestPrice(4, flights, 0, 3, 1) << " (Expected: 700)\n";
34 std::vector<std::vector<int>> flights2 = {{0,1,100},{1,2,100},{0,2,500}};
35 std::cout << "Direct Flight Test: " << sol.findCheapestPrice(3, flights2, 0, 2, 0) << " (Expected: 500)\n";
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(K * E)
  • Space complexity: O(V)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS / Backtracking with PruningO(V^(K + 1))O(V)Recursively explores flight paths up to depth k + 1 with branch-and-bound pruning.Combinatorial path branching
2.BFS Level-by-Level Queue RelaxationO(K * E)O(V + E)Level-order traversal where each level corresponds to exactly 1 flight hop.Queue expansions
3.Bellman-Ford with Snapshot CopyOptimalO(K * E)O(V)Relaxes all edges for exactly k + 1 rounds using cloned snapshot arrays.Edge scan loop

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Modifying the same price array during Bellman-Ford without snapshotting, causing multi-hop chaining in a single round.

Pitfall 2:

Using standard Dijkstra with a simple boolean visited array, which discards paths with fewer stops.

Pitfall 3:

Confusing number of stops with number of edges: k stops allows k + 1 edges.

Crucial Edge Cases to Validate:

  • k = 0 (Direct flights only) — Loop runs for exactly 0 + 1 = 1 iteration, considering only single-edge direct flights from src.
  • Destination unreachable within k stops — prices[dst] remains infinity / 1e9, returning -1.
  • Graph contains cycles with cheaper paths — Snapshot copy ensures edges are incremented one hop per round, preventing infinite looping in cycles.
  • Direct flight exists but multi-hop flight is cheaper — Both are correctly considered as long as stops <= k; minimum price wins.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the edge translation immediately: 'At most k stops is mathematically equivalent to at most k + 1 edges.'
  2. Explain why standard Dijkstra fails: 'A cheaper path that uses too many stops can shadow an alternate path that has fewer stops and could have reached dst.'
  3. Present Bellman-Ford with snapshotting as the most bulletproof approach: 'Running k + 1 iterations with snapshot arrays uses only O(V) space and is immune to multi-edge cascade bugs.'

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does standard Dijkstra's algorithm fail to guarantee the optimal answer for this problem without modifying its state?

2.What is the primary reason for cloning the prices array into a temp snapshot at the beginning of each Bellman-Ford round?

3.How many edge relaxation rounds are required if at most k stops are allowed?

Back to DSA Sheet