Cheapest Flights Within K Stops

Problem in Plain English

Each flight links two cities with a price, and k caps how many intermediate stops a trip may use. Return the cheapest fare from the start city to the destination within that limit, or -1 when no such trip exists.

Problem Statement

There are n cities linked by flights, where flights[i] = [from, to, price] is a directed flight costing price. Given a start city src, a destination city dst, and an integer k, return the cheapest price of any trip from src to dst using at most k stops.

A stop is an intermediate city, so k stops means at most k + 1 flights. If no trip respects the limit, return -1.

Constraints

2 <= n <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= from, to < n
from != to
1 <= price <= 10^4
No two flights share the same (from, to) pair.
0 <= src, dst, k < n
src != dst

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

Trip 0 to 1 to 3 costs 700 with one stop, while the cheaper 400 route needs two stops and breaks the limit.

Example 2

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200

Trip 0 to 1 to 2 costs 200 with one stop, beating the direct 500 flight.

Example 3

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500

With zero stops allowed, only the direct 0 to 2 flight qualifies.

Intuition

The cheapest arrival at a city is not enough information: it may have spent too many flights to continue. In Example 1, 0 to 1 to 2 to 3 costs only 400 but uses three flights, while the two-flight budget permits 0 to 1 to 3 for 700. Enumerate budget-limited walks, or share their work by remembering the cheapest arrival at each city after each allowed flight count. A relaxation round extends only the previous round, so it cannot accidentally spend extra flights.

Approaches

DFS Every Route

Solution Details

Reveal DFS Every Route: intuition, complexity, and code

Intuition

Walk every trip that fits the stop budget and remember the cheapest arrival seen. Depth-first search naturally enumerates all short walks, but the number of walks explodes with each extra stop, which is the blowup the optimal approach avoids by sharing work across trips.

Step-by-Step Logic

Start at city 0 with 2 flights left (k + 1) and cost 0; the only outgoing flight is 0 -> 1 for 100.
Arrive at city 1 with 1 flight left and cost 100; outgoing flights are 1 -> 2 for 100 and 1 -> 3 for 600.
Follow 1 -> 2: arrive at city 2 with 0 flights left and cost 200, so stop without reaching the destination.
Return to city 1 and follow 1 -> 3: arrive at the destination with cost 700, so record best = 700 even though no flights remain.
No walks remain, so return best = 700.

Why It Works

At a call, cost is the sum of the chosen flights and left is the unused flight budget. Following each outgoing edge enumerates every possible next flight while reducing left by one. Destination arrivals are checked before the zero-budget condition, so a trip using exactly k + 1 flights is included. Every recorded cost is feasible. Since all prices are positive, a prefix costing at least best cannot improve best, and extending a destination arrival cannot help either. These pruned branches cannot contain a cheaper answer; if no arrival is recorded, no allowed trip exists.

Dry Run

DFS Every Route: variable states at each step
Event / path	City	Flights left	Cost	Best after	Decision
enter 0	0	2	0	inf	follow first edge 0 to 1
enter 0 to 1	1	1	100	inf	follow first edge 1 to 2
enter 0 to 1 to 2	2	0	200	inf	budget exhausted; return to 1
enter 0 to 1 to 3	3	0	700	700	destination checked first; return to 1
unwind 1 then 0	-	-	-	700	all outgoing branches explored
answer	-	-	-	700	return 700

Complexity Analysis

Time Complexity

O(n + E + n^{k+1})

Space Complexity

O(n + E + k)

Let E be the flight count. Building the adjacency map costs O(n + E) as a loose bound. With at most n - 1 outgoing choices per city, at most k + 1 flights give O(n^{k+1}) recursive work. Positive-cost pruning often saves work but does not remove exponential worst-case growth; this approach is educational, not suitable for unrestricted maximum dense inputs. The map and copied edge pairs use O(n + E) space, and the stack has at most k + 2 frames. Every accumulated fare is at most 1000000 and fits Java int.

Code

Solution.java

1import java.util.Map;2import java.util.List;3import java.util.HashMap;4import java.util.ArrayList;5
6class Solution {7    private int best;8
9    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {10        Map<Integer, List<int[]>> adj = new HashMap<>();11        for (int[] f : flights) {12            adj.computeIfAbsent(f[0], x -> new ArrayList<>()).add(new int[]{f[1], f[2]});13        }14        best = Integer.MAX_VALUE;15        dfs(adj, src, dst, k + 1, 0);16        return best == Integer.MAX_VALUE ? -1 : best;17    }18
19    private void dfs(Map<Integer, List<int[]>> adj, int node, int dst, int left, int cost) {20        // An arrival using the last permitted flight is still valid.21        if (node == dst) {22            best = Math.min(best, cost);23            return;24        }25        // Positive fares mean an already-expensive prefix cannot improve best.26        if (left == 0 || cost >= best || !adj.containsKey(node)) {27            return;28        }29        for (int[] e : adj.get(node)) {30            dfs(adj, e[0], dst, left - 1, cost + e[1]);31        }32    }33}

Hints

Hint 1

Plain shortest-path search ignores the stop budget, so a cheaper trip with too many stops can beat a valid one.

Hint 2

Exactly k + 1 flights fit the budget, which matches one extra flight of reach per relaxation round.

Hint 3

Copy the prices before each round so a round only extends trips that were already valid in the previous round.

Edge Cases

Start and destination disconnected, so prices stay infinite and the answer is -1.
k = 0, where only a direct flight qualifies and a single round decides the answer.
A cheap route needing too many stops, which must lose to a pricier valid route as in Example 1.
An empty flight list returns -1 because src and dst differ.
Directed flights cannot be traversed backward; cycles consume budget and positive fare without helping.
A route using exactly k + 1 flights is valid, including an arrival with zero budget left.

Common Mistakes and Interview Tips

Running plain Dijkstra without stop tracking, which returns the cheapest trip regardless of its stop count.
Relaxing into the same array being read, which chains several flights inside one round and smuggles in over-budget trips.
Looping k times instead of k + 1, which prices trips with one flight too few.
Marking a city globally visited in DFS loses arrivals with different costs or remaining budgets.
Interview tip: explain the at-most-flight-count invariant and why copying preserves shorter paths; a cheaper city arrival with more flights used does not dominate every other arrival.

Key Takeaway

When a shortest path also caps the edge count, limit the relaxation rounds to the cap instead of running the textbook algorithm to convergence.