Skip to main content
Talentd

Cheapest Flights Within K Stops - Solution & Explanation

MediumDynamic ProgrammingDepth-First SearchBreadth-First SearchGraph9 min readAsked at: Amazon, Microsoft, Apple +15
Practice this problem

Problem Statement

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

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.

 

Example 1:

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Example 2:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Example 3:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

 

Constraints:

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

Approach Overview

Problem Overview: You are given n cities connected by flights where each edge has a price. The task is to find the cheapest cost from src to dst using at most k stops. The challenge is balancing shortest-path logic with a constraint on the number of intermediate nodes.

Approach 1: Breadth-First Search with Cost Tracking (Time: O(E * K), Space: O(V + E))

This approach treats the graph as levels of stops and explores it using Breadth-First Search. Build an adjacency list from the flights array, then perform BFS where each level represents one additional stop. Maintain the current cost to each node and only continue exploring if the new path is cheaper than previously recorded costs. The key insight is limiting traversal depth to k + 1 edges while pruning expensive paths early. This keeps exploration efficient even if the graph has many connections.

Approach 2: Dijkstra's Algorithm with Stop Constraint (Time: O(E log (V * K)), Space: O(V * K))

This method adapts shortest path logic using a min-heap (priority queue). Instead of storing only the node and cost, the state also tracks how many stops were used to reach the node. The heap always expands the cheapest path first. When a node is popped, its neighbors are pushed with updated cost and stop count, as long as the stop limit has not been exceeded. This guarantees the cheapest valid route is discovered early and works well when flight graphs are dense.

Recommended for interviews: Interviewers usually expect the Dijkstra-style solution because it directly models the constrained shortest-path problem and demonstrates familiarity with priority queues. Starting with the BFS idea shows you understand graph traversal with level constraints, but implementing the heap-based approach shows stronger mastery of graph optimization techniques.

Approach 1: Breadth-First Search (BFS) with Cost Tracking

In this approach, use BFS to explore all possible paths. Utilize a queue to store the current node, accumulated cost, and the number of stops made so far. The key is to traverse by layer, effectively managing the permitted stops through levels of BFS. If we reach the destination within the allowed stops, track the minimum cost.

This solution constructs a graph from the flights list using an adjacency list. For BFS, a queue keeps track of the current city, the accumulated cost to reach that city, and the number of remaining stops allowed. Traverse each city, and only append a city to the queue if doing so reduces the cost to reach it. This ensures we explore the cheapest path first, within k stops. The process continues until all nodes are explored or the cheapest path is found.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n * k) in the worst case when every city is connected.
Space Complexity: O(n) for storing the graph and queue.

Try this approach in the editor →

Approach 2: Dijkstra's Algorithm Adaptation

This approach leverages a modified version of Dijkstra's algorithm to explore paths from source to destination using a prioritized data structure like a min-heap. Each entry tracks not only the cumulative cost but also the number of stops taken. The algorithm ensures the shortest paths are evaluated first and skips any path with exceeding stops, thus efficiently finding the minimum cost path within allowed stops.

This C++ solution utilizes a min-heap or priority queue data structure to maintain the current city, accumulated cost, and stops left. Priority ensures that cities with the smallest accumulated cost are processed first, following Dijkstra's logic but capped by the number of stops. Each step examines the target city, updating the cost and queuing potential paths until either the destination is reached within allowed stops or the queue is exhausted.

Code

C++Java

C++

Java

Complexity

Time Complexity: O((n+k) log n) reflects edge processing and heap operations.
Space Complexity: O(n) taken by the adjacency list and tracking structures.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Breadth-First Search (BFS) with Cost Tracking

Time Complexity: O(n * k) in the worst case when every city is connected.
Space Complexity: O(n) for storing the graph and queue.

Dijkstra's Algorithm Adaptation

Time Complexity: O((n+k) log n) reflects edge processing and heap operations.
Space Complexity: O(n) taken by the adjacency list and tracking structures.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS with Cost TrackingO(E * K)O(V + E)When the stop limit is small and you want a simple level-based traversal.
Dijkstra with Stop ConstraintO(E log (V * K))O(V * K)General case for weighted graphs where the cheapest path must respect stop limits.

Video Solution

G-38. Cheapest Flights Within K Stops • take U forward • 345,968 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Cheapest Flights Within K Stops easy or hard?
Cheapest Flights Within K Stops is classified as a Medium difficulty problem. The challenge comes from combining shortest-path algorithms with a constraint on the number of stops, which requires modifying standard BFS or Dijkstra techniques.
Cheapest Flights Within K Stops Python or Java solution
Python implementations usually use BFS with a deque or Dijkstra with the heapq module. Java solutions typically use a PriorityQueue for the Dijkstra approach and adjacency lists built with ArrayList. Both languages follow the same graph traversal logic with stop constraints.
How to solve Cheapest Flights Within K Stops in O(E*K)?
Use a breadth-first search traversal where each BFS level represents one stop. Maintain a cost array to track the cheapest known price to each city. When exploring neighbors, only update and push them if the new price is lower and the number of stops is within the allowed limit.
What is the best approach for Cheapest Flights Within K Stops?
The most reliable approach is a modified Dijkstra's algorithm using a priority queue. Each state tracks the current city, total cost, and number of stops used. The heap always expands the cheapest route first while ensuring the stop count never exceeds K. This approach runs in roughly O(E log (V*K)) time and works well for dense flight graphs.
Is Cheapest Flights Within K Stops asked at Google/Amazon/Meta?
Cheapest Flights Within K Stops is a common graph interview problem and has appeared in interviews at companies like Amazon and Google. It tests understanding of shortest-path algorithms, BFS level constraints, and priority queue optimizations.
What data structure is used in Cheapest Flights Within K Stops?
The main data structures are an adjacency list for the graph, a queue for the BFS solution, and a min-heap (priority queue) for the Dijkstra-based solution. Arrays or hash maps are also used to track the cheapest cost for each node and stop count.
What is the time complexity of Cheapest Flights Within K Stops?
The BFS with cost tracking approach runs in O(E*K) time because each edge may be explored up to K levels. The Dijkstra-based solution typically runs in O(E log (V*K)) due to heap operations while maintaining states for different stop counts.

Ready to solve this problem?

Practice Cheapest Flights Within K Stops with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Vacation Days

Next

Minimum Cost to Reach City With Discounts