98.Cheapest Flights Within K Stops

MediumGraphs · 19/19

Problem

There are n cities numbered 0 to n - 1 and a list of flights, where flights[i] = [from, to, price] is a one-way flight costing price.

Given src, dst and an integer k, return the cheapest price from src to dst using at most k stops (i.e. at most k + 1 flights). If no such route exists, return -1.

Examples

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: 0 -> 1 -> 3 costs 700 with 1 stop. 0 -> 1 -> 2 -> 3 costs 400 but needs 2 stops.

Input:  n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: 0 -> 1 -> 2 uses 1 stop and costs 200.

Input:  n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation: With 0 stops only the direct flight is allowed.

Constraints

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

💡 Key Insight

The stop limit breaks plain Dijkstra: the cheapest way to reach a city might use too many stops, and a pricier route with fewer stops could be the only one that still reaches dst in time. Bellman-Ford fits perfectly, because its i-th round computes the cheapest cost using at most i edges. Running exactly k + 1 rounds — and relaxing from a copy of the previous round's distances so one round never chains two flights — gives the answer directly.

Brute Force DFS

TimeO(d^(k+1))SpaceO(n + E)

Intuition

Try every route from src that uses at most k + 1 flights, tracking the cost so far, and keep the minimum cost seen on arrival at dst. Prune any branch whose cost already matches or exceeds the best answer.

Algorithm

Build an adjacency list from -> (to, price).
dfs(city, flightsLeft, cost): if city == dst, update best and return. If flightsLeft == 0 or cost >= best, return.
For each outgoing flight, recurse with flightsLeft - 1 and cost + price.
Return best, or -1 if it was never set.

Visualization

k = 1 (2 flights allowed), src = 0, dst = 3
0 -100-> 1 -600-> 3          cost 700  best = 700
0 -100-> 1 -100-> 2          no flights left, stop
best = 700

Code

java

import java.util.ArrayList;
import java.util.List;

class Solution {
    private List<List<int[]>> adj;
    private int best;
    private int dst;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] f : flights) {
            adj.get(f[0]).add(new int[] {f[1], f[2]});
        }
        this.dst = dst;
        best = Integer.MAX_VALUE;
        dfs(src, k + 1, 0); // k stops = k + 1 flights
        return best == Integer.MAX_VALUE ? -1 : best;
    }

    private void dfs(int city, int flightsLeft, int cost) {
        if (city == dst) {
            best = Math.min(best, cost);
            return;
        }
        if (flightsLeft == 0 || cost >= best) {
            return; // out of flights or already too expensive
        }
        for (int[] f : adj.get(city)) {
            dfs(f[0], flightsLeft - 1, cost + f[1]);
        }
    }
}

Complexity

Time: O(d^(k+1)) — d is the max out-degree; every route of up to k + 1 flights may be explored.
Space: O(n + E) — adjacency list plus recursion depth k + 1.

Dijkstra with Stop Tracking

TimeO(E · k · log(E · k))SpaceO(n + E · k)

Intuition

Push states (cost, city, flightsUsed) into a min-heap. Because states pop in cost order, the first time dst pops it is the cheapest valid answer. A city may need to be expanded more than once — a later (pricier) pop is still useful if it arrived with fewer flights. So we remember fewestFlights[city] among popped states and skip a state only if it is both pricier and no better on flights.

Algorithm

Build adjacency list; fewestFlights[] = INF; push (0, src, 0).
Pop (cost, city, used). If city == dst, return cost.
If used >= fewestFlights[city] or used == k + 1, skip. Otherwise set fewestFlights[city] = used.
Push (cost + price, next, used + 1) for every outgoing flight.
Return -1 when the heap empties.

Visualization

k = 1 (max 2 flights), src=0, dst=3
pop (0, 0, used 0)     push (100, 1, 1)
pop (100, 1, used 1)   push (200, 2, 2), (700, 3, 2)
pop (200, 2, used 2)   used == k+1 -> cannot fly further
pop (700, 3, used 2)   dst -> return 700

Code

java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] f : flights) {
            adj.get(f[0]).add(new int[] {f[1], f[2]});
        }

        int[] fewestFlights = new int[n];
        Arrays.fill(fewestFlights, Integer.MAX_VALUE);
        // heap of {cost, city, flightsUsed}
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        heap.offer(new int[] {0, src, 0});

        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int cost = top[0], city = top[1], used = top[2];
            if (city == dst) {
                return cost; // cheapest valid arrival
            }
            // a cheaper state already reached this city with no more flights
            if (used >= fewestFlights[city] || used == k + 1) {
                continue;
            }
            fewestFlights[city] = used;
            for (int[] f : adj.get(city)) {
                heap.offer(new int[] {cost + f[1], f[0], used + 1});
            }
        }
        return -1;
    }
}

Complexity

Time: O(E · k · log(E · k)) — each city can be expanded up to k + 1 times.
Space: O(n + E · k) — adjacency list and heap.

Bellman-Ford with k + 1 RoundsOptimal

TimeO(k · E)SpaceO(n)

Intuition

After round i of Bellman-Ford, prices[v] is the cheapest cost to reach v using at most i flights — provided each round reads only last round's values. Relaxing in place could chain two flights in a single round and silently exceed the stop limit, so each round writes into a copy temp. After k + 1 rounds, prices[dst] is the answer.

Algorithm

prices[] = INF, prices[src] = 0.
Repeat k + 1 times:
- temp = prices.clone().
- For each flight (u, v, p): if prices[u] != INF and prices[u] + p < temp[v], set temp[v].
- prices = temp.
Return prices[dst], or -1 if it is INF.

Dry Run

flowchart LR
    C0["0 (src)"] -->|"100"| C1["1"]
    C1 -->|"100"| C2["2"]
    C2 -->|"100"| C0
    C1 -->|"600"| C3["3 (dst)"]
    C2 -->|"200"| C3

k = 1 -> 2 rounds                 0     1     2     3
start                             0    INF   INF   INF
round 1 (<= 1 flight)             0    100   INF   INF
round 2 (<= 2 flights)            0    100   200   700
answer prices[3] = 700

(without the copy, round 1 would chain 0->1->2->3 and wrongly report 400)

Code

java

import java.util.Arrays;

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        final int INF = Integer.MAX_VALUE;
        int[] prices = new int[n];
        Arrays.fill(prices, INF);
        prices[src] = 0;

        for (int round = 0; round <= k; round++) { // k stops = k + 1 flights
            int[] temp = prices.clone(); // read old values, write new ones
            for (int[] f : flights) {
                int u = f[0], v = f[1], price = f[2];
                if (prices[u] != INF && prices[u] + price < temp[v]) {
                    temp[v] = prices[u] + price;
                }
            }
            prices = temp;
        }
        return prices[dst] == INF ? -1 : prices[dst];
    }
}

Complexity

Time: O(k · E) — k + 1 rounds over all flights.
Space: O(n) — two price arrays.

Complexity Comparison

Approach	Time	Space
Brute Force DFS	O(d^(k+1))	O(n + E)
Dijkstra with Stop Tracking	O(E · k · log(E · k))	O(n + E · k)
Bellman-Ford with k + 1 Rounds	O(k · E)	O(n)

Common Pitfalls

Confusing stops with flights: k stops means up to k + 1 edges.
Relaxing Bellman-Ford in place, which lets one round use several edges and breaks the stop limit.
Using plain Dijkstra with a single dist[] and a visited set — it discards pricier-but-shorter routes that may be the only valid ones.
Adding price to INF and overflowing; always check prices[u] != INF first.