LeetCode 787: Cheapest Flights Within K Stops Solution

Master LeetCode problem 787 (Cheapest Flights Within K Stops), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

787. Cheapest Flights Within K Stops

Medium

Dynamic Programming Depth-First Search Breadth-First Search Graph Heap (Priority Queue)Shortest Path

Problem Explanation

Explanation:

To solve this problem, we can use Dijkstra's algorithm with a slight modification to keep track of the number of stops. We will create a priority queue to store the cities along with the total cost and stops taken to reach that city. We will continuously explore the cities with the minimum cost until we reach the destination or exhaust the allowed number of stops.

Initialize a priority queue and add the source city with cost 0 and stops 0.
While the priority queue is not empty, pop the city with the minimum cost.
If the popped city is the destination, return the cost.
If the number of stops taken is more than k, continue to the next iteration.
Explore all the flights from the current city and add them to the priority queue with the updated cost and stops.
Repeat steps 2-5 until the priority queue is empty.
If no valid path is found, return -1.

Time Complexity: The time complexity of this approach is O(E log E), where E represents the number of edges in the graph.

Space Complexity: The space complexity is O(E) for the priority queue to store the cities.

Solution Code

import java.util.*;

class Solution {
    class City {
        int id;
        int cost;
        int stops;

        public City(int id, int cost, int stops) {
            this.id = id;
            this.cost = cost;
            this.stops = stops;
        }
    }

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] flight : flights) {
            graph.putIfAbsent(flight[0], new ArrayList<>());
            graph.get(flight[0]).add(new int[]{flight[1], flight[2]});
        }

        PriorityQueue<City> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.cost));
        pq.offer(new City(src, 0, 0));

        while (!pq.isEmpty()) {
            City curr = pq.poll();
            if (curr.id == dst) {
                return curr.cost;
            }
            if (curr.stops > k) {
                continue;
            }
            List<int[]> neighbors = graph.getOrDefault(curr.id, new ArrayList<>());
            for (int[] neighbor : neighbors) {
                pq.offer(new City(neighbor[0], curr.cost + neighbor[1], curr.stops + 1));
            }
        }

        return -1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 787 (Cheapest Flights Within K Stops)?

This page provides optimized solutions for LeetCode problem 787 (Cheapest Flights Within K Stops) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 787 (Cheapest Flights Within K Stops)?

The time complexity for LeetCode 787 (Cheapest Flights Within K Stops) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 787 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 787 in Java, C++, or Python.

Back to LeetCode Solutions