#787

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Cheapest Flights Within K Stops

Find the cheapest flight from a source to a destination with at most K stops using graph traversal techniques efficiently.

dynamic programming depth first search breadth first search graph heap priority queue

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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(n k). Space complexity varies: DFS recursion stack is O(n), BFS queue can be O(n k), 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.

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.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def findCheapestPrice(
        self, n: int, flights: List[List[int]], src: int, dst: int, k: int
    ) -> int:
        INF = 0x3F3F3F3F
        dist = [INF] * n
        dist[src] = 0
        for _ in range(k + 1):
            backup = dist.copy()
            for f, t, p in flights:
                dist[t] = min(dist[t], backup[f] + p)
        return -1 if dist[dst] == INF else dist[dst]

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def findCheapestPrice(
        self, n: int, flights: List[List[int]], src: int, dst: int, k: int
    ) -> int:
        INF = 0x3F3F3F3F
        dist = [INF] * n
        dist[src] = 0
        for _ in range(k + 1):
            backup = dist.copy()
            for f, t, p in flights:
                dist[t] = min(dist[t], backup[f] + p)
        return -1 if dist[dst] == INF else dist[dst]

Continue Practicing

#743 network delay time #399 evaluate division #329 longest increasing path in a matrix