Cheapest Flights Within K Stops

Medium

Apple

1 view

Topics:

GraphsDynamic Programming

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i, to_i, price_i] indicates that there is a flight from city from_i to city to_i with cost price_i.

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.

For example:

Given n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, and k = 1, the expected output is 700. The optimal path with at most 1 stop from city 0 to 3 is through city 1, with a cost of 100 + 600 = 700.

Another example:

Given n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, and k = 1, the expected output is 200. The optimal path with at most 1 stop from city 0 to 2 is through city 1, with a cost of 100 + 100 = 200.

Can you write a function to solve this problem efficiently, considering the constraints that 1 <= n <= 100, 0 <= flights.length <= (n * (n - 1) / 2), and 0 <= k < n?

Cheapest Flights Within K Stops

Medium

Apple

1 view

Topics:

GraphsDynamic Programming

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i, to_i, price_i] indicates that there is a flight from city from_i to city to_i with cost price_i.

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.

For example:

Given n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, and k = 1, the expected output is 700. The optimal path with at most 1 stop from city 0 to 3 is through city 1, with a cost of 100 + 600 = 700.

Another example:

Given n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, and k = 1, the expected output is 200. The optimal path with at most 1 stop from city 0 to 2 is through city 1, with a cost of 100 + 100 = 200.

Can you write a function to solve this problem efficiently, considering the constraints that 1 <= n <= 100, 0 <= flights.length <= (n * (n - 1) / 2), and 0 <= k < n?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the number of cities (n) and the number of flights? What is the range for the price of a flight?
Is it possible for there to be cycles in the flight routes?
Is it possible for src and dst to be the same city? If so, what should the return value be?
If multiple routes exist with the same cheapest price and at most k stops, is any one of those acceptable?
Is it possible for the flight list to be empty, or for the source/destination to be invalid cities (i.e., not within the range of 0 to n-1)?

Brute Force Solution

Approach

The brute force approach to finding the cheapest flight within K stops means we explore every possible route from the starting city to the destination, making sure we don't exceed the allowed number of stops. We calculate the cost for each route and keep track of the cheapest one found so far. We examine all feasible paths to find the solution.

Here's how the algorithm would work step-by-step:

Start at the origin city.
List all the direct flights you can take from the origin city.
For each of those flights, list all the flights you can take from the city you arrive at, continuing the journey.
Keep repeating this process, finding all possible sequences of flights.
Each time you add a flight to the sequence, make sure you haven't exceeded the maximum allowed number of stops (K). If you have, stop exploring that particular sequence of flights.
If a sequence of flights reaches the destination city, calculate the total cost of that route.
Compare the cost of the newly found route to the cheapest route you've found so far. If the new route is cheaper, remember its cost as the new cheapest cost.
After exploring all possible routes within the allowed number of stops, the cheapest cost you've remembered is the answer.

Code Implementation

def find_cheapest_price_brute_force(number_of_cities,
    flights, source_city, destination_city, max_stops):

    cheapest_price_found = float('inf')

    def depth_first_search(current_city, current_stops,
        current_cost, current_path):
        nonlocal cheapest_price_found

        # If we've reached the destination, update the cheapest price.
        if current_city == destination_city:
            cheapest_price_found = min(
                cheapest_price_found, current_cost)
            return

        # Prune search if we exceed the maximum allowed stops.
        if current_stops > max_stops:
            return

        for start_city, end_city, price in flights:
            if start_city == current_city:

                # Avoid cycles by checking if city already in path
                if end_city not in current_path:
                    depth_first_search(
                        end_city, current_stops + 1,
                        current_cost + price, current_path + [end_city])

    # Start the depth-first search from the source city.
    depth_first_search(source_city, 0, 0, [source_city])

    # If no path was found, return -1.
    if cheapest_price_found == float('inf'):
        return -1
    else:
        return cheapest_price_found

Big(O) Analysis

Time Complexity

O(n^(k+1)) – In the brute force approach, we are essentially exploring all possible paths of length up to k+1 (where k is the maximum number of stops) in a graph where n represents the number of cities. In the worst-case scenario, each city could be connected to every other city. Therefore, at each step of exploring a path, we potentially have n choices for the next city. Since we can take up to k+1 steps (flights), the total number of possible paths we explore grows exponentially with k, specifically as n multiplied by itself k+1 times (n * n * ... * n, k+1 times). Hence, the time complexity is O(n^(k+1)).

Space Complexity

O(N^K) – The brute force approach uses a recursive call stack to explore all possible flight sequences. In the worst-case scenario, where almost all cities are connected, the branching factor at each level of recursion can be close to the number of cities, N. The recursion depth is limited by K, the maximum number of stops. Therefore, the maximum size of the call stack can grow up to N^K, where N is the number of cities and K is the maximum number of stops. This stems from exploring all paths of length K from all possible starting points. Consequently, the space complexity is O(N^K).

Optimal Solution

Approach

To find the cheapest flight with a limited number of stops, we'll use a modified shortest-path finding technique. Instead of exploring all flight combinations, we smartly track the best known price to reach each city at each number of stops. This helps us avoid re-exploring routes that are already more expensive.

Here's how the algorithm would work step-by-step:

Start by knowing the price to reach the starting city, which is zero.
Keep track of the current best prices for reaching each city, given a certain number of stops.
For each possible flight, consider whether using that flight lowers the cost to reach the destination city, given the number of stops used so far.
If a flight provides a cheaper route to a city within the allowed number of stops, update the best-known price for that city and number of stops.
Repeat this process, considering all flights and incrementing the number of stops until you reach the maximum allowed stops.
After checking all flights and stop combinations, the cheapest price to the destination city within the maximum stops is the answer. If you couldn't reach the destination within the constraints, it means there's no viable route.

Code Implementation

def find_cheapest_price(number_of_cities, flights, source_city, destination_city, max_stops):
    cheapest_prices = {}
    cheapest_prices[source_city] = 0

    # Track costs for each city at each stop count.
    for stop_count in range(max_stops + 1): 
        temp_cheapest_prices = cheapest_prices.copy()

        for source, destination, price in flights:
            if source in cheapest_prices:
                if destination not in temp_cheapest_prices:
                    temp_cheapest_prices[destination] = float('inf')

                # Update price if cheaper path found with current stop count
                if cheapest_prices[source] + price < temp_cheapest_prices[destination]:

                    temp_cheapest_prices[destination] = cheapest_prices[source] + price

        cheapest_prices = temp_cheapest_prices

    # If destination not reachable, return -1
    if destination_city not in cheapest_prices:
        return -1

    return cheapest_prices[destination_city]

Big(O) Analysis

Time Complexity

O(K * |E|) – The algorithm iterates up to K+1 times (where K is the maximum number of stops) to consider paths with 0 to K stops. In each iteration, it examines all edges |E| in the flight graph to see if taking an edge can result in a cheaper path to a destination city, given the current number of stops. Thus, the time complexity is proportional to the product of K and the number of edges, or K * |E|. This assumes that updating the cost to reach a destination takes constant time.

Space Complexity

O(N) – The algorithm maintains a data structure to track the current best prices for reaching each city, given a certain number of stops. This data structure, in the worst case, needs to store the best price for each city for each possible number of stops. If we represent the number of cities as N and the maximum allowed stops as K, this would result in a space requirement of N * (K+1). However, since the plain English explanation doesn't explicitly mention storing price for each stop count K, the primary driver for auxillary space is the best prices for each city with no stop consideration. Therefore, we store at most the best price for each city to reach the destination. Thus we store intermediate results for N cities leading to an auxiliary array of size N. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty flights array	Return -1 immediately since there are no flights to consider, indicating no possible route.
src and dst are the same city	If source and destination are the same, the price is 0, unless k is negative in which case there is no valid solution so return -1.
k is 0 and there is no direct flight from src to dst	Return -1 since no stops are allowed and there's no direct flight.
No path exists between src and dst within k stops	The algorithm should eventually exhaust all possible paths within k stops and return -1 if no path is found.
Graph contains cycles	The algorithm should avoid infinite loops by limiting the number of stops to k, effectively pruning the search when a cycle is encountered beyond k stops.
Large number of cities and flights, potentially leading to integer overflow in price calculations	Use long data type or modular arithmetic to prevent integer overflow during price calculations.
k is very large (close to n-1), potentially causing performance issues	Consider optimizing the algorithm, such as using a priority queue with a visited set, to reduce redundant exploration of less promising paths.
Flights array contains duplicate flights (same from, to, and price)	The algorithm should handle duplicate flights correctly, treating them as a single flight option.