787. Cheapest Flights Within K Stops
Cheapest Flights Within K Stops (LeetCode 787) 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.
How to solve Cheapest Flights Within K Stops
Cheapest Flights Within K Stops is a Bellman-Ford and BFS with K Stops problem, part of Graph Traversal Patterns (DFS & BFS). Find shortest paths with constraints using Bellman-Ford algorithm and BFS with limited stops.
Work towards the solution in these steps:
- Consider representing the cities and flights as a graph where nodes are cities and edges are flights with associated costs.
- Think about using a graph traversal technique like BFS or Dijkstra to explore possible flight paths from the source city.
- Since there's a constraint on the maximum number of stops (k), modify your traversal to track and limit the number of stops made so far.
The reference solution runs in O((|E| + |V|) * log|V|) time and O(|E| + |V|) space.
The Cheapest Flights Within K Stops solution and editorial walks through the full approach with reference code.
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 <= 10^4
- 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|) time and O(|E| + |V|) 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
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Shortest Path (Bellman-Ford / BFS+K) subpattern
- The full DSA patterns 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:
- Shortest Path with Alternating Colors — Medium, same subpattern
- Accounts Merge — Medium, same pattern
- Alien Dictionary — Hard, same pattern
- All Paths from Source Lead to Destination — Medium, same pattern
- Build a Matrix With Conditions — Hard, same pattern
- Bus Routes — Hard, same pattern
Cheapest Flights Within K Stops FAQ
What is the LeetCode number of Cheapest Flights Within K Stops?
Cheapest Flights Within K Stops is LeetCode problem 787, rated Medium.
What pattern is used to solve Cheapest Flights Within K Stops?
Cheapest Flights Within K Stops is a Bellman-Ford and BFS with K Stops problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Shortest Path (Bellman-Ford / BFS+K) subpattern.
What is the time complexity of Cheapest Flights Within K Stops?
The reference solution runs in O((|E| + |V|) * log|V|) time and O(|E| + |V|) space.
Which companies ask Cheapest Flights Within K Stops?
Cheapest Flights Within K Stops has been reported in interviews at Facebook, Expedia, Apple, Airbnb, Amazon.