Cheapest Flights Within K Stops Leetcode Problem [Python Solution]

If you're preparing for technical interviews or simply looking to enhance your algorithmic skills, you've come to the right place.

In this guide, we'll delve into the LeetCode problem titled Cheapest Flights Within K Stops (Problem 787).

This is a medium-difficulty problem falling under the category of Advanced Graphs, and it's often used in interviews by companies like Google.

We'll explore the problem, break it down step by step, and provide you with an efficient Python solution.

Problem Overview

The problem statement is as follows:

You are given n cities connected by some number of flights.

Each flight is represented by an array flights, where flights[i] = [from_i, to_i, price_i] indicates a flight from city from_i to city to_i with a cost of price_i.

Additionally, you are given three integers: src (the source city), dst (the destination city), and k (the maximum number of stops allowed).

Your task is to find the cheapest price to travel from src to dst with at most k stops.

If it's impossible to reach the destination with the given constraints, return -1. Let's illustrate the problem with an example.

Example:

n = 4
flights = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]]
src = 0
dst = 3
k = 1

In this example, we have 4 cities connected by flights as shown in the graph.

The optimal path with at most 1 stop from city 0 to 3 is marked in red and has a cost of 100 + 600 = 700. Note that the path through cities [0, 1, 2, 3] is cheaper but is invalid because it uses 2 stops.

Constraints:

• 1 <= n <= 100
• 0 <= flights.length <= (n * (n - 1) / 2)
• flights[i].length == 3
• 0 <= from_i, to_i < n
• from_i != to_i
• 1 <= price_i <= 104
• There will not be multiple flights between two cities.
• 0 <= src, dst, k < n
• src != dst

Now that we understand the problem, let's tackle it step by step.

Understanding the Constraints

Before diving into the solution, it's crucial to understand the problem's constraints.

These constraints provide information about the problem's input size and limits, helping us design an efficient solution.

Let's go through them briefly:

1. n represents the number of cities, which can vary from 1 to 100. This tells us the size of the graph.
2. The flights array can contain up to (n * (n - 1) / 2) flights, indicating the number of edges in the graph.

Flights have a source city, a destination city, and a price.
3. The price of a flight, price_i, is in the range from 1 to 10,000, which is a reasonable price range for flights.
4. src and dst are the source and destination cities, respectively, with values ranging from 0 to n-1.
5. k is the maximum number of stops allowed, which also has a limit from 0 to n-1.

This constraint is essential for our algorithm.

Now, with a clear understanding of the problem and its constraints, let's move on to the solution.

Cheapest Flights Within K Stops LeetCode Problem Solution

To solve this problem efficiently, we'll use the Bellman-Ford algorithm.

The Bellman-Ford algorithm is a dynamic programming approach that can handle weighted graphs and negative weights.

In our case, we'll adapt it to find the cheapest price to reach the destination city while considering the maximum number of stops, k.

Let's break down our approach into multiple sections:

1. Bruteforce Approach

The brute-force approach involves exploring all possible paths from the source to the destination, considering the constraints on the number of stops.

However, this approach becomes impractical for large graphs because it results in an exponential number of path combinations.

Hence, we'll use the Bellman-Ford algorithm to solve the problem efficiently.

2. Efficient Approach with Bellman-Ford Algorithm

The Bellman-Ford algorithm is based on the principle of relaxation.

We'll initialize an array prices to store the minimum prices to reach each city.

The size of this array is n, and we'll initialize all prices to positive infinity, except for the source city, which has a price of 0. Then, we'll iterate k+1 times, representing the maximum number of stops allowed.

In each iteration, we'll go through all flights (edges) in the graph and update the minimum price to reach each city.

We'll use the relaxation process to check if we've found a shorter path to each city and update the price accordingly.

Here's the Python code for this approach:

def findCheapestPrice(n, flights, src, dst, k):
    # Initialize prices array with infinity
    prices = [float("inf")] * n
    prices[src] = 0  # Price to reach the source city is 0

    for i in range(k + 1):
        tempPrices = prices.copy()  # Create a temporary array to track updates

        for s, d, p in flights:  # s=source, d=destination, p=price
            if prices[s] == float("inf"):
                continue  # Skip cities that cannot be reached
            if prices[s] + p < tempPrices[d]:
                tempPrices[d] = prices[s] + p

        prices = tempPrices  # Update the main prices array

    return -1 if prices[dst] == float("inf") else prices[dst]

This code implements the Bellman-Ford algorithm to find the minimum price to reach the destination city with at most k stops.

If it's not possible to reach the destination with the given constraints, we return -1.

Time and Space Complexity

Let's analyze the time and space complexity of our solution:

Time Complexity: The time complexity of our solution is O(k * E), where k is the maximum number of stops allowed, and E is the number of edges (flights) in the graph.

The reason is that we perform k+1 iterations, and in each iteration, we go through all the edges.

Space Complexity: The space complexity is O(n), where n is the number of cities.

We use an array prices of size n to store the minimum prices for each city.

Reasoning Behind Our Approach

Our approach efficiently utilizes the Bellman-Ford algorithm to find the cheapest flights within the given constraints.

Here's a brief explanation of our reasoning:

• We initialize an

  array prices to keep track of the minimum prices to reach each city.

Since we aim to find the cheapest price to reach the destination, this array is essential.

• We start with the source city and set its price to 0. This is the basis for our algorithm, as the price to reach the source city is 0.

• We iterate k+1 times, as k represents the maximum number of stops allowed.

In each iteration, we update the minimum prices based on the flights (edges) available.

• Within each iteration, we create a temporary array tempPrices to track the updates without affecting the main prices array.

This is essential because the updates should be simultaneous for all cities in each iteration.

• We go through all flights (edges) and check if the price to reach the source city plus the price of the flight is lower than the current minimum price to reach the destination city.

If it is, we update the minimum price.

• After each iteration, we update the main prices array with the values from tempPrices.

• Finally, we check if it's possible to reach the destination city within the given constraints.

If the price to reach the destination city is still infinity, it means it's not reachable, and we return -1. Otherwise, we return the minimum price.

Related Interview Questions By Company:

• Unique Paths LeetCode
• Sort An Array LeetCode
• Maximum Sum Circular Subarray LeetCode

Related Interview Questions By Difficulty:

• Cheapest Flights Within K Stops LeetCode
• Alien Dictionary LeetCode
• Min Cost To Connect All Points LeetCode

Related Interview Questions By Category:

• Palindromic Substrings LeetCode
• Maximal Square LeetCode
• Minimum Path Sum LeetCode

Conclusion

The Cheapest Flights Within K Stops problem (LeetCode Problem 787) is a challenging graph problem that can be efficiently solved using the Bellman-Ford algorithm.

By understanding the problem constraints and implementing the provided Python solution, you can find the cheapest price to reach the destination city with the maximum number of stops allowed.

This problem not only tests your algorithmic skills but also your ability to optimize solutions for real-world scenarios.

Happy coding!