Cheapest Flights Within K Stops

MediumGraphs · Shortest Path with Hop Limit🧩 Shortest Paths LeetCode #787 ↗Updated Oct 30, 2026

Problem

There are n cities and one-way flights flights[i] = [from, to, price]. Find the cheapest trip from src to dst that makes at most k intermediate stops (i.e. uses at most k + 1 flights). Return -1 if no such trip exists.

Input[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1Output200

Inputsame flights, k=0Output500

1 ≤ n ≤ 100 · 1 ≤ price ≤ 10⁴ · no duplicate flights · 0 ≤ k < n · src ≠ dst

Try it yourself

Java

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The hop limit breaks plain Dijkstra (a cheaper route may use too many flights). Bellman–Ford fits naturally: after round i, dist holds the cheapest cost using at most i flights — just stop after k + 1 rounds.

PatternShortest Paths

Instinct Weighted edges plus "minimum cost, time or effort to reach" - grab a min-heap and always expand the cheapest unsettled node next (Dijkstra).

Memory hack Pop the cheapest, skip the stale, relax the rest - Dijkstra is a ripple in a pond that touches near shores before far ones.

Open the Shortest Paths guide →

Approaches

Brute ForceDFS Over All Routes (with Cost Pruning)

Time O(d^k+1)Space O(n + E)

Try every route of at most k + 1 flights from src, keeping the best cost seen at dst. Prune a branch once its cost already reaches the best answer. d = max out-degree.

Java

private int best = Integer.MAX_VALUE;

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]});
    dfs(adj, src, dst, k + 1, 0);
    return best == Integer.MAX_VALUE ? -1 : best;
}
private void dfs(List<List<int[]>> adj, int city, int dst, int flightsLeft, int cost) {
    if (city == dst) { best = cost; return; } // pruning guarantees cost < best
    if (flightsLeft == 0) return;
    for (int[] e : adj.get(city))
        if (cost + e[1] < best) dfs(adj, e[0], dst, flightsLeft - 1, cost + e[1]);
}

Correct, but the number of routes explodes exponentially with k.

BetterDijkstra on (city, flights used) States

Time O(kE log(kE))Space O(n + kE)

Pop states {cost, city, used} cheapest-first; the first pop of dst is the answer. A city popped again is only useful if it arrives with fewer flights than before (it is already more expensive), so each city expands at most k + 1 times.

Java

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[] fewest = new int[n]; // fewest flights used when a city was expanded
    Arrays.fill(fewest, Integer.MAX_VALUE);
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, src, 0}); // {cost, city, flights used}
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int cost = cur[0], city = cur[1], used = cur[2];
        if (city == dst) return cost;
        if (used > k || used >= fewest[city]) continue;
        fewest[city] = used;
        for (int[] e : adj.get(city)) pq.offer(new int[]{cost + e[1], e[0], used + 1});
    }
    return -1;
}

Fast in practice, but the heap adds a log factor over Bellman–Ford.

OptimalBellman–Ford, k + 1 Rounds

Time O(k · (n + E))Space O(n)

Run exactly k + 1 relaxation rounds. Each round reads from the previous round's copy, so a single round can extend a path by only one flight — that is what enforces the stop limit.

Java

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    for (int round = 0; round <= k; round++) { // round r allows r + 1 flights
        int[] next = dist.clone();
        for (int[] f : flights)
            if (dist[f[0]] != Integer.MAX_VALUE && dist[f[0]] + f[2] < next[f[1]])
                next[f[1]] = dist[f[0]] + f[2];
        dist = next;
    }
    return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}

Simple, no heap, tight worst-case bound — the cleanest answer.

Pro tip

Relaxing in place (no clone()) lets one round chain several flights and silently breaks the k limit.

At a glance

Level	Approach	Time	Space
Brute Force	DFS Over All Routes (with Cost Pruning)	`O(d^k+1)`	`O(n + E)`
Better	Dijkstra on (city, flights used) States	`O(kE log(kE))`	`O(n + kE)`
Optimal	Bellman–Ford, k + 1 Rounds	`O(k · (n + E))`	`O(n)`

Common pitfalls

Off-by-one: k stops = k + 1 flights/rounds.
Plain Dijkstra with only dist[city] discards a pricier-but-shorter route.
Bellman–Ford without a copy of the previous round exceeds the stop limit.

Interview tips

Explain why vanilla Dijkstra fails here with a tiny counter-example.
Frame Bellman–Ford as DP: dp[i][v] = cheapest with ≤ i flights.
BFS by levels with a cost array is an equivalent O(k·E) alternative.

Pattern

Bounded-hop shortest path → Bellman–Ford for exactly k+1 rounds, or Dijkstra on (node, hops).

My notes saved in this browser