How to Solve Cheapest Flights Within K Stops

This problem requires finding the minimum cost to travel from the source city to the destination with at most K stops. Leveraging depth-first search with pruning, breadth-first search levels, or dynamic programming memoization ensures efficiency. Carefully managing stops and visited states prevents invalid paths and reduces unnecessary computation.

Problem Statement

You are given n cities numbered from 0 to n-1 and a list of flights where flights[i] = [fromi, toi, pricei] indicates a flight from city fromi to city toi with cost pricei. Your task is to determine the minimum cost to travel from a given source city src to a destination city dst with at most k stops. If no such route exists, return -1.

Implement an algorithm that explores all valid paths while respecting the stop constraint. 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 cheapest valid path costs 700 using at most one stop.

Examples

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

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

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

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

Solution Approach

Depth-First Search with Pruning

Use DFS to explore all paths from src to dst, keeping track of the current cost and stops. Prune paths exceeding the maximum stops or current minimum cost to avoid redundant computation.

Breadth-First Search with Level Tracking

Perform BFS using a queue to explore cities level by level. Track the number of stops at each level and the accumulated cost to ensure paths exceeding K stops are ignored while maintaining the cheapest route found.

Dynamic Programming / Memoization

Store the minimum cost to reach each city with a certain number of stops in a DP table or map. Reuse computed results to prevent recomputation of overlapping subproblems, combining graph traversal with efficient memoization.

Complexity Analysis

Time complexity depends on the approach: DFS can reach O(n^k) in worst case without pruning, BFS is O(n + flights.length) per level, and DP reduces repeated computations to O(nk). Space complexity varies: DFS recursion stack is O(n), BFS queue can be O(nk), and DP table requires O(n*k) space.

What Interviewers Usually Probe

• The candidate understands graph traversal constraints and pruning techniques.
• Candidate explains how stops limitation affects path exploration and algorithm choice.
• Shows awareness of time-space trade-offs for DFS, BFS, and DP in this problem context.

Common Pitfalls or Variants

Common pitfalls

• Ignoring the maximum stop constraint leads to invalid cheaper paths being selected.
• Failing to prune higher-cost paths early causes exponential blow-up in DFS.
• Recomputing subproblems without memoization increases runtime unnecessarily.

Follow-up variants

• Allow flights with unlimited stops and optimize for shortest cost using standard Dijkstra's algorithm.
• Return the number of different cheapest paths instead of the minimum cost.
• Change the cost metric to include flight durations or combined price-duration trade-offs.

How GhostInterview Helps

• Automatically tracks stop counts and costs to ensure valid DFS or BFS path exploration.
• Highlights pruning opportunities and memoization points to reduce computation.
• Generates clear step-by-step reasoning tied to the exact DFS graph traversal pattern for interview clarity.

Topic Pages

• Dynamic Programming
• Depth-First Search
• Breadth-First Search
• Graph
• Heap (Priority Queue)
• Shortest Path

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main strategy to solve Cheapest Flights Within K Stops?

Use DFS or BFS with careful stop tracking, combined with memoization to efficiently find the minimum cost path without exceeding K stops.

How do I handle paths that exceed the allowed number of stops?

Prune any path where the stop count exceeds K during DFS or BFS, ensuring only valid routes contribute to the minimum cost calculation.

Can Dijkstra's algorithm be applied to this problem?

Yes, but it must be modified to track stops explicitly since classic Dijkstra's assumes unlimited edges without stop constraints.

What common mistakes occur when implementing DFS for this problem?

Common mistakes include not tracking stops correctly, revisiting cities without stop limits, or failing to prune paths with higher cumulative cost.

Is dynamic programming necessary for Cheapest Flights Within K Stops?

DP is not strictly necessary but highly recommended to store minimum costs per city per stop level, reducing repeated computation and improving efficiency.