How do you solve Cheapest Flights Within K Stops on LeetCode?

Cheapest Flights Within K Stops (LeetCode #787) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(E log E) time complexity and O(V) space complexity. Key insight: Using a priority queue optimizes the search for the cheapest path.

What is the brute force solution for Cheapest Flights Within K Stops?

The brute force approach for Cheapest Flights Within K Stops is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach explores all possible paths from the source city to the destination city, considering all flights and stops. This method guarantees finding the cheapest price but is inefficient due to its exhaustive nature. The optimal Optimal Solution approach improves this to O(E log E).

What are the interview tips for Cheapest Flights Within K Stops?

Clarify the constraints and edge cases before coding. Discuss the trade-offs between different approaches. Explain your thought process as you code.

What are common mistakes when solving Cheapest Flights Within K Stops?

Not considering the number of stops correctly. Failing to handle cases where no valid path exists.

#787

Cheapest Flights Within K Stops

Medium

Dynamic ProgrammingDepth-First SearchBreadth-First SearchGraph TheoryHeap (Priority Queue)Shortest PathGraph TraversalPriority Queue

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(E log E)
Space	O(1)	O(V)

💡

Intuition

Time O(E log E)Space O(V)

The optimal solution uses a modified Dijkstra's algorithm with a priority queue to efficiently find the cheapest flights while keeping track of the number of stops. This approach significantly reduces the number of paths explored compared to brute force.

⚙️

Algorithm

4 steps

1Step 1: Create a priority queue to store the current cost, city, and number of stops.
2Step 2: Initialize the queue with the source city and cost 0.
3Step 3: While the queue is not empty, pop the city with the lowest cost and check if it's the destination.
4Step 4: If it's not the destination and the number of stops is less than or equal to k, push all neighboring cities into the queue with updated costs and incremented stops.

solution.py19 lines

1# Full working Python code
2import heapq
3from collections import defaultdict
4
5class Solution:
6    def findCheapestPrice(self, n, flights, src, dst, k):
7        graph = defaultdict(list)
8        for u, v, price in flights:
9            graph[u].append((v, price))
10
11        pq = [(0, src, 0)]  # (cost, city, stops)
12        while pq:
13            cost, city, stops = heapq.heappop(pq)
14            if city == dst:
15                return cost
16            if stops <= k:
17                for neighbor, price in graph[city]:
18                    heapq.heappush(pq, (cost + price, neighbor, stops + 1))
19        return -1

ℹ

Complexity note: The time complexity is O(E log E) due to the priority queue operations, where E is the number of edges (flights). The space complexity is O(V) for storing the graph representation.

1Using a priority queue optimizes the search for the cheapest path.
2Graph representation helps in efficiently managing flight connections.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.