LeetCode Solutions Blog

Cheapest Flights Within K Stops

Number: 803

Difficulty: Medium

Paid? No

Problem Description

Given a graph of n cities and a list of flights—each represented as [from, to, price]—find the cheapest flight route from a source city (src) to a destination city (dst) with at most k stops. If no such route exists, return -1.

Key Insights

Use a variant of BFS combined with a min-heap (priority queue) to always expand the cheapest route.
Each state in the queue includes the current cost, current city, and the number of stops used so far.
Track the best-known cost to reach a city with a certain number of stops to prune non-optimal routes.
Ensure that you do not exceed k stops during exploration.

Space and Time Complexity

Time Complexity: O(E log(E)) in the worst-case scenario, where E is the number of flights, due to the heap operations. Space Complexity: O(n + E) for storing the graph and auxiliary data structures like the heap and best-cost map.

Solution

We solve the problem using a modified Dijkstra's algorithm. The approach employs a min-heap to ensure that we always process the state with the lowest cumulative cost next. Each state tracks the total cost so far, the current city, and the number of stops made. When a state reaches the destination city, we return its cost. To avoid unnecessary work, we record the lowest cost at which each city has been reached with a given number of stops. This state-tracking helps prune routes that are more expensive or exceed the allowed number of stops.

Code Solutions

import heapq

def findCheapestPrice(n, flights, src, dst, k):
    # Build graph: each city maps to a list of (neighboring city, flight price)
    graph = {i: [] for i in range(n)}
    for from_city, to_city, price in flights:
        graph[from_city].append((to_city, price))
    
    # Priority queue: (total_cost, current_city, stops so far)
    heap = [(0, src, 0)]
    
    # Dictionary to store the best cost to reach a city with a given stop count
    best = {}
    
    while heap:
        cost, city, stops = heapq.heappop(heap)
        # Return cost if destination is reached
        if city == dst:
            return cost
        
        # If the current number of stops exceeds k, skip further processing
        if stops > k:
            continue
        
        # Expand the neighboring flights
        for neighbor, price in graph[city]:
            new_cost = cost + price
            # Only proceed if this route is cheaper or not yet explored for this many stops
            if (neighbor, stops + 1) not in best or new_cost < best[(neighbor, stops + 1)]:
                best[(neighbor, stops + 1)] = new_cost
                heapq.heappush(heap, (new_cost, neighbor, stops + 1))
    return -1

# Example usage:
print(findCheapestPrice(4, [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], 0, 3, 1))