Cheapest Flights Within K Stops
MedPrompt
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 <= 104- There will not be any multiple flights between two cities.
0 <= src, dst, k < nsrc != dst
Approaches
3 approaches with complexity analysis and trade-offs.
This is a straightforward recursive approach. We explore every possible path from the source src to the destination dst. We keep track of the number of stops and the cumulative cost along each path. If a path reaches the destination within the allowed k stops, we compare its cost with the minimum cost found so far and update it if necessary. To avoid getting stuck in cycles and exploring excessively long paths, we prune any path that exceeds k stops.
Algorithm
- Build an adjacency list representation of the graph where
adj[u]contains pairs of(v, price)for each flight fromutov. - Initialize a global variable
minCostto infinity. - Define a recursive function
dfs(u, dst, maxEdges, edges, cost). - Start the search by calling
dfs(src, dst, k + 1, 0, 0). - Inside
dfs: a. Ifedges > maxEdges, prune the path as it has too many flights. b. Ifu == dst, a valid path is found. UpdateminCost = min(minCost, cost). c. For each neighborvofuwith flight pricep: i. Ifcost + p > minCost, prune this sub-path as it's not optimal. ii. Recursively calldfs(v, dst, maxEdges, edges + 1, cost + p). - After the initial call returns, if
minCostis still infinity, it means the destination is unreachable. Return -1, otherwise returnminCost.
Walkthrough
First, we represent the graph using an adjacency list, where adj[i] stores a list of pairs (neighbor, price) for all flights departing from city i.
We initialize a global variable minCost to a very large value.
We then start a recursive DFS from the source city. The DFS function dfs(city, edges, cost) takes the current city, the number of flights taken so far, and the current path cost as arguments. Note that k stops means a path can have at most k+1 flights.
The base cases for the recursion are:
- If
edges > k + 1, we have exceeded the flight limit. - If the current
cityis thedst, we have found a valid route. We updateminCost = min(minCost, cost). In the recursive step, we iterate through all the neighbors of the current city. For each neighbor, we make a recursive call, incrementing the edge count and adding the flight price to the cost. A simple optimization is to prune a path if its current cost already exceedsminCost. This approach is very slow because it may explore the same city multiple times through different paths, leading to an exponential time complexity.
class Solution { int minCost = Integer.MAX_VALUE; List<int[]>[] adj; public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { adj = new ArrayList[n]; for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); } for (int[] flight : flights) { adj[flight[0]].add(new int[]{flight[1], flight[2]}); } // k stops means k+1 edges dfs(src, dst, k + 1, 0, 0); return minCost == Integer.MAX_VALUE ? -1 : minCost; } private void dfs(int u, int dst, int maxEdges, int edges, int cost) { if (edges > maxEdges) { return; } if (u == dst) { minCost = Math.min(minCost, cost); return; } for (int[] flight : adj[u]) { int v = flight[0]; int price = flight[1]; if (cost + price > minCost) { // Pruning continue; } dfs(v, dst, maxEdges, edges + 1, cost + price); } }}Complexity
Time
O(n^(k+1)). In the worst case, the search tree can have a branching factor of up to `n-1` and a depth of `k+1`.
Space
O(k+n+E). The space is dominated by the recursion stack depth, which can go up to `k+1`, and the space for the adjacency list, which is `O(n+E)`.
Trade-offs
Pros
Conceptually simple and easy to implement.
Cons
Extremely inefficient due to re-visiting nodes and exploring an exponential number of paths.
Will likely result in a Time Limit Exceeded (TLE) error on most competitive programming platforms for non-trivial inputs.
This problem can be modeled as a shortest path problem on an expanded state graph. A standard Dijkstra's algorithm finds the shortest path based only on cost, but here we also have a constraint on the number of stops. We can incorporate the number of stops into the state definition. The state in our search will be (city, flights_taken). We use a priority queue to always explore the path with the minimum cost first.
Algorithm
- Model the problem on a state graph where each node is a pair
(city, stops). - Build an adjacency list for the flight graph.
- Use a priority queue to store
(cost, city, stops), prioritized bycost. - Use a 2D array
minCosts[n][k+2]to store the minimum cost to reach a city with a certain number of flights. Initialize it with infinity. - Push the starting state
(0, src, 0)into the priority queue, where 0 is the number of flights taken.minCosts[src][0] = 0. - While the priority queue is not empty:
a. Pop the state with the minimum cost:
(cost, u, flights_taken). b. Ifu == dst, returncost. c. Ifflights_taken > k, this path has too many stops, so skip it. d. For each neighborvofuwith flight pricep: i. Calculate the new state:(cost + p, v, flights_taken + 1). ii. Ifcost + pis less thanminCosts[v][flights_taken + 1], it's a better path. iii. UpdateminCosts[v][flights_taken + 1] = cost + pand push the new state to the priority queue. - If the queue becomes empty and the destination was not reached, return -1.
Walkthrough
The state we'll use in our priority queue is a tuple (cost, city, flights). The priority queue will be ordered by cost. A path with k stops has k+1 flights.
We need to keep track of the minimum cost to reach each city with a specific number of flights to avoid cycles and redundant computations. A 2D array, minCosts[city][flights], can be used for this purpose.
The algorithm proceeds as follows:
- Build an adjacency list for the graph.
- Initialize a priority queue and add the starting state:
{cost=0, city=src, flights=0}. - Initialize the
minCostsarray with infinity. SetminCosts[src][0] = 0. - While the priority queue is not empty, extract the state
{cost, u, flights}with the smallestcost. - If
uis the destinationdst, we have found the cheapest path that satisfies the stop constraint, so we can returncost. Dijkstra's nature ensures this is the first time we reachdstwith the overall minimum cost. - If the number of
flightsis greater thank+1, we cannot continue this path. - For each neighbor
vofu, we calculate the new cost and flights. If this new path tov(withflights + 1) is cheaper than any previously found path tovwith the same number of flights, we updateminCosts[v][flights + 1]and push the new state{newCost, v, flights + 1}to the priority queue. This approach is much more efficient than brute-force DFS because it intelligently prunes search paths using costs and stop counts, guided by the priority queue.
class Solution { public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { List<int[]>[] adj = new ArrayList[n]; for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); } for (int[] flight : flights) { adj[flight[0]].add(new int[]{flight[1], flight[2]}); } int[][] minCosts = new int[n][k + 2]; for (int[] row : minCosts) { Arrays.fill(row, Integer.MAX_VALUE); } // PQ stores {cost, city, flights_taken} PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); pq.offer(new int[]{0, src, 0}); minCosts[src][0] = 0; while (!pq.isEmpty()) { int[] curr = pq.poll(); int cost = curr[0]; int u = curr[1]; int flights_taken = curr[2]; if (u == dst) { return cost; } if (flights_taken > k) { // k stops means k+1 flights continue; } for (int[] neighbor : adj[u]) { int v = neighbor[0]; int price = neighbor[1]; if (cost + price < minCosts[v][flights_taken + 1]) { minCosts[v][flights_taken + 1] = cost + price; pq.offer(new int[]{cost + price, v, flights_taken + 1}); } } } return -1; }}Complexity
Time
O(E*k + n*k*log(n*k)). The number of states is `n * (k+1)`. Each state is pushed to the priority queue. For each popped state, we iterate its neighbors. The complexity is dominated by priority queue operations on `n*k` states and relaxing `E*k` edges.
Space
O(n*k + E). `O(n*k)` for the `minCosts` array and the priority queue, and `O(n+E)` for the adjacency list.
Trade-offs
Pros
Much more efficient than brute-force search.
Guaranteed to find the optimal solution due to the nature of Dijkstra's algorithm.
Cons
More complex to implement than a simple DFS or Bellman-Ford.
The time and space complexity depends on
k, which can be large.
This problem has an optimal substructure and overlapping subproblems, making it suitable for dynamic programming. The Bellman-Ford algorithm's structure is a natural fit. The standard Bellman-Ford algorithm finds the shortest paths from a source by iteratively relaxing all edges. After i iterations, it guarantees to find the shortest path containing at most i edges. We can adapt this to our problem, as "at most k stops" is equivalent to "at most k+1 edges".
Algorithm
- Create an array
costsof sizento store the minimum cost to reach each city. - Initialize
costs[src] = 0and all other elements to infinity. - Loop from
i = 0tok(fork+1iterations, representing up tok+1edges). a. Create a temporary arraytempCostsas a copy ofcosts. b. For each flight[u, v, price]in theflightsarray: i. If the source of the flightuis reachable (costs[u]is not infinity), update the cost to reachv:tempCosts[v] = min(tempCosts[v], costs[u] + price). c. After checking all flights, updatecostswithtempCosts. - After the loop,
costs[dst]contains the result. If it's infinity, return -1; otherwise, return the value.
Walkthrough
We'll use a 1D array, costs, where costs[i] stores the minimum cost to reach city i from the source src.
We initialize costs[src] to 0 and all other costs[i] to infinity.
We then run a loop k+1 times. Each iteration i of this loop calculates the minimum costs for paths with at most i edges.
Inside the loop, we create a temporary copy of the costs array, say tempCosts. This is crucial because the calculations for paths of length i must be based on the results for paths of length i-1, not the partially updated results of length i.
We iterate through every flight [u, v, price]. If city u was reachable in the previous iteration (i.e., costs[u] is not infinity), we try to relax the edge to v. This means we update tempCosts[v] with min(tempCosts[v], costs[u] + price).
After iterating through all flights, we copy tempCosts back to costs. This completes one iteration.
After k+1 iterations, costs[dst] will hold the minimum cost to reach the destination with at most k stops. If it's still infinity, the destination is unreachable.
This approach is efficient and relatively simple to implement.
class Solution { public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { // dist[i] = min cost to reach city i int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0; // k stops means k+1 edges. We run k+1 iterations. for (int i = 0; i <= k; i++) { int[] temp = Arrays.copyOf(dist, n); for (int[] flight : flights) { int u = flight[0]; int v = flight[1]; int price = flight[2]; if (dist[u] != Integer.MAX_VALUE) { temp[v] = Math.min(temp[v], dist[u] + price); } } dist = temp; } return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst]; }}Complexity
Time
O((k+1) * E), where `E` is the number of flights. We have an outer loop that runs `k+1` times and an inner loop that iterates through all `E` flights.
Space
O(n). We need two arrays of size `n` to store the costs for the current and previous iterations.
Trade-offs
Pros
Generally more efficient than the Dijkstra-based approach for this problem.
Simple and clean implementation without complex data structures like priority queues.
Cons
May perform redundant work by iterating over all edges in every iteration, even those not on a promising path.
Solutions
Solution
class Solution { private static final int INF = 0x3f3f3f3f ; public int findCheapestPrice ( int n , int [][] flights , int src , int dst , int k ) { int [] dist = new int [ n ]; int [] backup = new int [ n ]; Arrays . fill ( dist , INF ); dist [ src ] = 0 ; for ( int i = 0 ; i < k + 1 ; ++ i ) { System . arraycopy ( dist , 0 , backup , 0 , n ); for ( int [] e : flights ) { int f = e [ 0 ], t = e [ 1 ], p = e [ 2 ]; dist [ t ] = Math . min ( dist [ t ], backup [ f ] + p ); } } return dist [ dst ] == INF ? - 1 : dist [ dst ]; } }class Solution { public: int findCheapestPrice ( int n , vector < vector < int >>& flights , int src , int dst , int k ) { const int inf = 0x3f3f3f3f ; vector < int > dist ( n , inf ); vector < int > backup ; dist [ src ] = 0 ; for ( int i = 0 ; i < k + 1 ; ++ i ) { backup = dist ; for ( auto & e : flights ) { int f = e [ 0 ], t = e [ 1 ], p = e [ 2 ]; dist [ t ] = min ( dist [ t ], backup [ f ] + p ); } } return dist [ dst ] == inf ? - 1 : dist [ dst ]; } };class Solution : def findCheapestPrice ( self , n : int , flights : List [ List [ int ]], src : int , dst : int , k : int ) -> int : INF = 0x3F3F3F3F dist = [ INF ] * n dist [ src ] = 0 for _ in range ( k + 1 ): backup = dist . copy () for f , t , p in flights : dist [ t ] = min ( dist [ t ], backup [ f ] + p ) return - 1 if dist [ dst ] == INF else dist [ dst ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.