algoadvance

Leetcode 787. Cheapest Flights Within K Stops

Problem Statement

You are given a series of flights 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. You need to find the cheapest price from the city src to the city dst with at most k stops. If there is no such route, return -1.

Example

Example 1:

Example 2:

Clarifying Questions

  1. Q: Can cities be revisited? A: No, the same city cannot be revisited according to constraints of cycles in Dijkstra’s algorithm.

  2. Q: Are there any limits on the number of cities or flights? A: The constraints typically are given in the full problem statement on LeetCode. However, for optimal implementation, we can generally expect n and flights to be reasonably large but within computational limit for algorithms like DFS, BFS, or Dijkstra’s with priority queue.

  3. Q: Is the graph directed or undirected? A: The graph representing flights is a directed graph because a flight from A to B does not imply a flight from B to A.

Strategy

We can approach this problem using a modified Dijkstra’s algorithm with a priority queue (min-heap). The priority queue will help efficiently fetch the current minimum cost route. Additionally, tracking the number of stops helps ensure the k stop condition is met.

Steps

  1. Create an adjacency list from flights.
  2. Use a priority queue to store tuples of the format (cost, current_city, stops).
  3. Start by pushing the source city (0, src, 0) into the priority queue.
  4. Use a while loop to extract the minimum cost route from the priority queue:
    • If the current city is the destination and stops are within the allowed limit, return the cost.
    • If the number of stops is less than k + 1, push all neighboring cities into the priority queue with updated costs and stops.
  5. If the loop ends without finding the destination within k stops, return -1.

Code

#include <vector>
#include <queue>
#include <unordered_map>
#include <tuple>

using namespace std;

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
    // Create the adjacency list
    unordered_map<int, vector<pair<int, int>>> graph;
    for (const auto& flight : flights) {
        graph[flight[0]].emplace_back(flight[1], flight[2]);
    }
    
    // Priority queue: (cost, current_node, stops)
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
    pq.emplace(0, src, 0);
    
    // Vector to track minimum cost to reach each city with a given number of stops
    vector<vector<int>> min_cost(n, vector<int>(k + 2, INT_MAX));
    min_cost[src][0] = 0;
    
    while (!pq.empty()) {
        auto [cost, curr_city, stops] = pq.top();
        pq.pop();
        
        if (curr_city == dst) return cost;
        
        // If we have more stops available
        if (stops <= k) {
            for (const auto& [neighbor, price] : graph[curr_city]) {
                int new_cost = cost + price;
                // If we find a cheaper cost path or if we're visiting the neighbor with fewer stops.
                if (new_cost < min_cost[neighbor][stops + 1]) {
                    min_cost[neighbor][stops + 1] = new_cost;
                    pq.emplace(new_cost, neighbor, stops + 1);
                }
            }
        }
    }
    
    return -1;
}

Time Complexity

Overall, the time complexity is O((V + E) log(V + E)), making the solution efficient even for relatively large inputs.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI