Cheapest Flights Within K Stops

Cheapest Flights Within K Stops is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Shortest Path (Bellman-Ford / BFS+K) subpattern.

Problem statement

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 <= 100

- 0 <= flights.length <= (n (n - 1) / 2)

- flights[i].length == 3

- 0 <= fromi, toi < n

- fromi != toi

- 1 <= pricei <= 104

- There will not be any multiple flights between two cities.

- 0 <= src, dst, k < n

- src != dst

Topics and companies

Topics: Dynamic Programming, Depth-First Search, Breadth-First Search, Graph, Heap (Priority Queue), Shortest Path.

Reported in interviews at Facebook, Expedia, Apple, Airbnb, Amazon.

How to practise Cheapest Flights Within K Stops on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O((|E| + |V|) * log|V|) = O(|E| * log|V|) time and O(|E| + |V|) = O(|E|) space.

Open Cheapest Flights Within K Stops in the code editor, or read the Cheapest Flights Within K Stops editorial for a worked solution with its approach and complexity analysis.

Where Cheapest Flights Within K Stops sits in the DSA pattern sheet

Problems related to Cheapest Flights Within K Stops

Other problems that use the same Shortest Path (Bellman-Ford / BFS+K) and Graph Traversal Patterns (DFS & BFS) techniques:

Preparing this workspace.