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: The graph is shown above. The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700. Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.
Example 2:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 Output: 200 Explanation: The graph is shown above. The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.
Example 3:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0 Output: 500 Explanation: The graph is shown above. The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.
Constraints:
1 <= n <= 1000 <= flights.length <= (n * (n - 1) / 2)flights[i].length == 30 <= fromi, toi < nfromi != toi1 <= pricei <= 1040 <= src, dst, k < nsrc != dstThe problem can be modeled as a weighted directed graph where cities are nodes and flights are edges with costs. The key challenge is finding the cheapest route from source to destination while using at most K stops. A common strategy is a modified Dijkstra’s algorithm using a priority queue that tracks the current cost, node, and number of stops used. Instead of only minimizing distance, we also ensure the number of stops does not exceed the limit.
Another effective method is a Bellman-Ford style dynamic programming approach, where we relax all edges up to K + 1 times. Each iteration represents taking one additional flight, ensuring that only paths within the stop constraint are considered.
Both strategies rely on graph traversal and cost updates. Priority queue methods typically perform faster in practice, while the DP relaxation approach is easier to reason about for bounded path lengths.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Modified Dijkstra / BFS with Priority Queue | O(E log V) | O(V + E) |
| Bellman-Ford (K-limited Relaxation) | O(K * E) | O(V) |
take U forward
In this approach, use BFS to explore all possible paths. Utilize a queue to store the current node, accumulated cost, and the number of stops made so far. The key is to traverse by layer, effectively managing the permitted stops through levels of BFS. If we reach the destination within the allowed stops, track the minimum cost.
Time Complexity: O(n * k) in the worst case when every city is connected.
Space Complexity: O(n) for storing the graph and queue.
1from collections import deque, defaultdict
2
3def find_cheapest_price(n, flights, src, dst, k):
4 adj_list = defaultdict(list)
5 for start, end, price in flights:
6 adj_list[start].append((end, price))
7
8 # (current city, current cost, remaining stops)
9 queue = deque([(src, 0, k + 1)])
10
11 min_cost = float('inf')
12
13 while queue:
14 position, cost, stops = queue.popleft()
15 if position == dst:
16 min_cost = min(min_cost, cost)
17 continue
18 if stops > 0:
19 for neighbor, price in adj_list[position]:
20 if cost + price < min_cost:
21 queue.append((neighbor, cost + price, stops - 1))
22 return min_cost if min_cost != float('inf') else -1This solution constructs a graph from the flights list using an adjacency list. For BFS, a queue keeps track of the current city, the accumulated cost to reach that city, and the number of remaining stops allowed. Traverse each city, and only append a city to the queue if doing so reduces the cost to reach it. This ensures we explore the cheapest path first, within k stops. The process continues until all nodes are explored or the cheapest path is found.
This approach leverages a modified version of Dijkstra's algorithm to explore paths from source to destination using a prioritized data structure like a min-heap. Each entry tracks not only the cumulative cost but also the number of stops taken. The algorithm ensures the shortest paths are evaluated first and skips any path with exceeding stops, thus efficiently finding the minimum cost path within allowed stops.
Time Complexity: O((n+k) log n) reflects edge processing and heap operations.
Space Complexity: O(n) taken by the adjacency list and tracking structures.
1#include <queue>
2#include <vector>
3#include <unordered_map>
4#include <limits.h>
5
using namespace std;
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
unordered_map<int, vector<pair<int, int>>> adj;
for (auto f : flights) {
adj[f[0]].push_back({f[1], f[2]});
}
typedef tuple<int, int, int> T;
priority_queue<T, vector<T>, greater<T>> pq;
pq.push({0, src, k+1});
while (!pq.empty()) {
auto [cost, city, stops] = pq.top(); pq.pop();
if (city == dst) return cost;
if (stops > 0) {
for (auto& [nextCity, price] : adj[city]) {
pq.push({cost + price, nextCity, stops - 1});
}
}
}
return -1;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is a popular graph question in technical interviews. It tests knowledge of shortest path algorithms, graph traversal, and how to handle constraints like limited stops.
A common optimal approach uses a modified Dijkstra's algorithm with a priority queue. It tracks both the current cost and the number of stops taken to ensure the route does not exceed K stops while still minimizing total price.
Yes, a Bellman-Ford style dynamic programming approach works well. By relaxing all edges up to K+1 times, you ensure that only routes within the allowed number of flights are considered.
A priority queue (min-heap) is commonly used to always expand the cheapest path first. It helps efficiently process cities based on the current accumulated flight cost while keeping track of remaining stops.
This C++ solution utilizes a min-heap or priority queue data structure to maintain the current city, accumulated cost, and stops left. Priority ensures that cities with the smallest accumulated cost are processed first, following Dijkstra's logic but capped by the number of stops. Each step examines the target city, updating the cost and queuing potential paths until either the destination is reached within allowed stops or the queue is exhausted.