787. Cheapest Flights Within K Stops LeetCode Solution
In this guide, you will get 787. Cheapest Flights Within K Stops LeetCode Solution with the best time and space complexity. The solution to Cheapest Flights Within K Stops problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
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.
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
Complexity Analysis
Time Complexity: O((|V| + |E|)\log |V|)
Space Complexity: O(|V| + |E|)
787. Cheapest Flights Within K Stops LeetCode Solution in C++
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst,
int k) {
vector<vector<pair<int, int>>> graph(n);
for (const vector<int>& flight : flights) {
const int u = flight[0];
const int v = flight[1];
const int w = flight[2];
graph[u].emplace_back(v, w);
}
return dijkstra(graph, src, dst, k);
}
private:
int dijkstra(const vector<vector<pair<int, int>>>& graph, int src, int dst,
int k) {
vector<vector<int>> dist(graph.size(), vector<int>(k + 2, INT_MAX));
dist[src][k + 1] = 0;
using T = tuple<int, int, int>; // (d, u, stops)
priority_queue<T, vector<T>, greater<>> minHeap;
minHeap.emplace(dist[src][k + 1], src, k + 1);
while (!minHeap.empty()) {
const auto [d, u, stops] = minHeap.top();
minHeap.pop();
if (u == dst)
return d;
if (stops == 0 || d > dist[u][stops])
continue;
for (const auto& [v, w] : graph[u])
if (d + w < dist[v][stops - 1]) {
dist[v][stops - 1] = d + w;
minHeap.emplace(dist[v][stops - 1], v, stops - 1);
}
}
return -1;
}
}; /* code provided by PROGIEZ */
787. Cheapest Flights Within K Stops LeetCode Solution in Java
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
List<Pair<Integer, Integer>>[] graph = new List[n];
for (int i = 0; i < n; i++)
graph[i] = new ArrayList<>();
for (int[] flight : flights) {
final int u = flight[0];
final int v = flight[1];
final int w = flight[2];
graph[u].add(new Pair<>(v, w));
}
return dijkstra(graph, src, dst, k);
}
private int dijkstra(List<Pair<Integer, Integer>>[] graph, int src, int dst, int k) {
int[][] dist = new int[graph.length][k + 2];
Arrays.stream(dist).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
dist[src][k + 1] = 0;
Queue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])) {
{ offer(new int[] {dist[src][k + 1], src, k + 1}); } // (d, u, stops)
};
while (!minHeap.isEmpty()) {
final int d = minHeap.peek()[0];
final int u = minHeap.peek()[1];
final int stops = minHeap.poll()[2];
if (u == dst)
return d;
if (stops == 0 || d > dist[u][stops])
continue;
for (Pair<Integer, Integer> pair : graph[u]) {
final int v = pair.getKey();
final int w = pair.getValue();
if (d + w < dist[v][stops - 1]) {
dist[v][stops - 1] = d + w;
minHeap.offer(new int[] {dist[v][stops - 1], v, stops - 1});
}
}
}
return -1;
}
} // code provided by PROGIEZ
787. Cheapest Flights Within K Stops LeetCode Solution in Python
class Solution:
def findCheapestPrice(
self,
n: int,
flights: list[list[int]],
src: int,
dst: int,
k: int,
) -> int:
graph = [[] for _ in range(n)]
for u, v, w in flights:
graph[u].append((v, w))
return self._dijkstra(graph, src, dst, k)
def _dijkstra(
self,
graph: list[list[tuple[int, int]]],
src: int,
dst: int,
k: int,
) -> int:
dist = [[math.inf] * (k + 2) for _ in range(len(graph))]
dist[src][k + 1] = 0
minHeap = [(dist[src][k + 1], src, k + 1)] # (d, u, stops)
while minHeap:
d, u, stops = heapq.heappop(minHeap)
if u == dst:
return d
if stops == 0 or d > dist[u][stops]:
continue
for v, w in graph[u]:
if d + w < dist[v][stops - 1]:
dist[v][stops - 1] = d + w
heapq.heappush(minHeap, (dist[v][stops - 1], v, stops - 1))
return -1 # code by PROGIEZ
