What is the brute force approach and complexity for Cheapest Flights Within K Stops?

Depth-first search over all trips with at most k + 1 flights; keep the cheapest that lands on dst with time complexity O(N^(K + 1)) and space complexity O(N + E).

What is the optimal approach and complexity for Cheapest Flights Within K Stops?

Relax every flight once per round for k + 1 rounds; each round reads last round's prices from a copy with optimal time complexity O(K · E) and space complexity O(N).

How do you identify the pattern for Cheapest Flights Within K Stops?

Look for key signals in the prompt: "cheapest price" indicates Each flight adds a price, so the total is a sum along the trip. This is a weighted shortest-path question.; "at most k stops" indicates A limit on the number of flights. Dijkstra can't count flights, so the limit needs rounds.; "return -1 if no such trip" indicates Some cities stay ∞ after the rounds, so they must be checked before returning..

Cheapest Flights Within K Stops

Medium·LeetCode #787Basic Anchor

LeetCode

Jump:

30-Second Mental ModelShortest Paths (weighted): Bellman-Ford with an edge limit

Complexity:O(N^(K + 1))→O(K · E)

Key Insight

Keep dist[c], the cheapest price to city c found so far (∞ if none). Repeat k + 1 times: copy dist into next, then go over every flight u → v with price w. If dist[u] + w < next[v], set next[v] = dist[u] + w. At the end of the round, dist = next. The answer is dist[dst]. The copy is what makes each round add exactly one flight.

Core Validity Invariant

A flight may extend only a price that was already in dist at the start of the round. So each round adds exactly one flight to a trip, and after round r every entry of dist is the cheapest price with at most r flights.

Problem

There are n cities, numbered 0 to n − 1, and a list of one-way flights. Each flight is [from, to, price]. You start in city src and want to fly to city dst.

Find the cheapest total price of a trip from src to dst that makes at most k stops. A stop is a city you land in between your start and your end, so k stops means at most k + 1 flights. If no trip fits, return -1.

Input

n (the number of cities), flights (a list of [from, to, price]), src, dst and k.

Output

The cheapest price from src to dst with at most k stops, or -1 if no such trip exists.

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 trip 0 → 1 → 3 costs 100 + 600 = 700 and has one stop (city 1). The trip 0 → 1 → 2 → 3 costs only 400, but it has two stops, so it is not allowed.

Example 2

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

Output: 200

The trip 0 → 1 → 2 costs 100 + 100 = 200 and has one stop. The direct flight 0 → 2 costs 500.

Example 3

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

Output: 500

With no stops you can only take the direct flight 0 → 2, which costs 500.

Constraints

• 2 ≤ n ≤ 100
• 0 ≤ flights.length ≤ n · (n − 1) / 2
• flights[i].length == 3
• 0 ≤ from, to < n, and from ≠ to
• 1 ≤ price ≤ 10^4
• There are never two flights between the same pair of cities.
• 0 ≤ src, dst, k < n
• src ≠ dst

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
With k = 1, how many flights can a trip use? Which cities can it land on in between?
2.
Plain Dijkstra keeps one cheapest route per city. Can the cheapest route to a city also be the one that uses the most flights?
3.
If I know the cheapest price to every city using at most 2 flights, how do I get the cheapest price using at most 3?
4.
When I update a city's price during one pass over the flights, should a flight I just used in that same pass be allowed to extend the next flight?
5.
How many passes over the flights do I need for k stops?

Brute force approach

Idea

Start at src and follow every outgoing flight, one at a time. Each path adds its price and uses one more flight. When a path lands on dst, record its price. A path that has already used k + 1 flights stops there. The answer is the smallest recorded price.

Thinking process

1
A trip is a chain of flights, and it may visit the same city more than once. So we can simply try every chain that has at most k + 1 flights.
2
Check it on example 2: n = 3, src = 0, dst = 2, k = 1, so at most 2 flights. From 0 there are two flights: 0 → 1 (100) and 0 → 2 (500). The first one lands on 1, then 1 → 2 (100) lands on 2 with a total of 200 and 2 flights. The second one lands on 2 at once with 500. The smallest recorded price is 200.
3
Each flight can lead to any of the other cities, so the number of trips grows very fast with k. This is fine for the tiny tests, but not for n = 100 and large k.
4
Record the price only when the trip lands on dst, and never use a trip with more than k + 1 flights.

Code & Implementation

brute.cpp

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        adj.assign(n, {});
        for (auto& f : flights) adj[f[0]].push_back({f[1], f[2]});
        best = INT_MAX;
        // k stops = k + 1 flights. Try every possible next flight at every step.
        dfs(src, dst, k + 1, 0);
        return best == INT_MAX ? -1 : best;
    }

private:
    vector<vector<pair<int, int>>> adj;   // adj[u] = {v, price}
    int best;

    void dfs(int city, int dst, int flightsLeft, int cost) {
        if (city == dst) best = min(best, cost);
        if (flightsLeft == 0) return;
        for (auto [v, price] : adj[city]) dfs(v, dst, flightsLeft - 1, cost + price);
    }
};

import java.util.*;

class Solution {
    private List<List<int[]>> adj;   // adj[u] = {v, price}
    private int best;

    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]});
        }
        best = Integer.MAX_VALUE;
        // k stops = k + 1 flights. Try every possible next flight at every step.
        dfs(src, dst, k + 1, 0);
        return best == Integer.MAX_VALUE ? -1 : best;
    }

    private void dfs(int city, int dst, int flightsLeft, int cost) {
        if (city == dst) best = Math.min(best, cost);
        if (flightsLeft == 0) return;
        for (int[] next : adj.get(city)) {
            int v = next[0], price = next[1];
            dfs(v, dst, flightsLeft - 1, cost + price);
        }
    }
}

from typing import List, Tuple

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        adj: List[List[Tuple[int, int]]] = [[] for _ in range(n)]   # adj[u] = (v, price)
        for u, v, price in flights:
            adj[u].append((v, price))

        best = float('inf')

        # k stops = k + 1 flights. Try every possible next flight at every step.
        def dfs(city: int, flightsLeft: int, cost: int) -> None:
            nonlocal best
            if city == dst:
                best = min(best, cost)
            if flightsLeft == 0:
                return
            for v, price in adj[city]:
                dfs(v, flightsLeft - 1, cost + price)

        dfs(src, k + 1, 0)
        return -1 if best == float('inf') else int(best)

export function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
    const adj: [number, number][][] = Array.from({ length: n }, () => []);   // adj[u] = [v, price]
    for (const [u, v, price] of flights) {
        adj[u].push([v, price]);
    }

    let best = Infinity;

    // k stops = k + 1 flights. Try every possible next flight at every step.
    function dfs(city: number, flightsLeft: number, cost: number): void {
        if (city === dst) best = Math.min(best, cost);
        if (flightsLeft === 0) return;
        for (const [v, price] of adj[city]) {
            dfs(v, flightsLeft - 1, cost + price);
        }
    }

    dfs(src, k + 1, 0);
    return best === Infinity ? -1 : best;
}

Complexity

Time O(N^(K + 1))Space O(N + E)

K is the stop limit k, N the number of cities and E the number of flights. Each of the k + 1 flights can go to any of the other N − 1 cities, so the search has about N^(k + 1) trips to check. The adjacency list stores each flight once, and the recursion goes at most k + 1 levels deep.

Optimized approach

Idea

Start from brute force

The brute force tries every trip with at most k + 1 flights. Many trips reach the same city with the same number of flights, and brute force explores everything after that city again for each of them.

Find the repeated work

For each city, the only thing that matters for the next flight is the cheapest price to reach it with the flights used so far. Brute force keeps every trip instead, so the same city and flight count are handled again and again.

Define the state — what variables do I need?

dist: dist[c] = the cheapest price to city c found so far, using at most the flights of the rounds that are finished. ∞ when no trip is known.
next: The copy written during the current round. It starts equal to dist, and it is the only array this round writes.
round: Round r lets every trip use r flights. We run k + 1 rounds.

Define validity

Define the transitions — when does each pointer move, and why is it safe?

Before the first round

dist[src] = 0; every other city is ∞

With zero flights you can only be at src, and it costs nothing.

The start of each round

next = dist (copy)

The copy is where this round writes. Reading from dist keeps a flight from building on a price that was just written in the same round.

Each flight u → v with price w, where dist[u] is not ∞

next[v] = min(next[v], dist[u] + w)

dist[u] is the price at the end of the last round. Adding w gives a trip with one more flight than the trips that end at u.

The end of each round

dist = next

The next round starts from trips with at most one more flight than before.

After k + 1 rounds

return dist[dst], or -1 if it is ∞

No round after the last allowed one is run, so no trip with more than k + 1 flights is counted.

What does the current window add to the answer?

Each round lets every trip use one more flight. The answer dist[dst] after k + 1 rounds is the cheapest trip with at most k + 1 flights, which is at most k stops.

Code & Implementation

optimal.cpp

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        const int INF = INT_MAX;
        vector<int> dist(n, INF);
        dist[src] = 0;

        // Round r lets every route use one more flight. k stops = k + 1 flights = k + 1 rounds.
        for (int round = 0; round <= k; round++) {
            // Copy: this round may only extend LAST round's routes, never a route
            // that already got a new flight earlier in this same round.
            vector<int> next = dist;
            for (auto& f : flights) {
                int u = f[0], v = f[1], price = f[2];
                if (dist[u] != INF && dist[u] + price < next[v]) next[v] = dist[u] + price;
            }
            dist = next;
        }
        return dist[dst] == INF ? -1 : dist[dst];
    }
};

import java.util.*;

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

        // Round r lets every route use one more flight. k stops = k + 1 flights = k + 1 rounds.
        for (int round = 0; round <= k; round++) {
            // Copy: this round may only extend LAST round's routes, never a route
            // that already got a new flight earlier in this same round.
            int[] next = dist.clone();
            for (int[] f : flights) {
                int u = f[0], v = f[1], price = f[2];
                if (dist[u] != INF && dist[u] + price < next[v]) {
                    next[v] = dist[u] + price;
                }
            }
            dist = next;
        }
        return dist[dst] == INF ? -1 : dist[dst];
    }
}

from typing import List

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        INF = float('inf')
        dist = [INF] * n
        dist[src] = 0

        # Round r lets every route use one more flight. k stops = k + 1 flights = k + 1 rounds.
        for _ in range(k + 1):
            # Copy: this round may only extend LAST round's routes, never a route
            # that already got a new flight earlier in this same round.
            nxt = list(dist)
            for u, v, price in flights:
                if dist[u] != INF and dist[u] + price < nxt[v]:
                    nxt[v] = dist[u] + price
            dist = nxt

        return -1 if dist[dst] == INF else int(dist[dst])

export function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
    const INF = Infinity;
    let dist: number[] = new Array(n).fill(INF);
    dist[src] = 0;

    // Round r lets every route use one more flight. k stops = k + 1 flights = k + 1 rounds.
    for (let round = 0; round <= k; round++) {
        // Copy: this round may only extend LAST round's routes, never a route
        // that already got a new flight earlier in this same round.
        const next = [...dist];
        for (const [u, v, price] of flights) {
            if (dist[u] !== INF && dist[u] + price < next[v]) {
                next[v] = dist[u] + price;
            }
        }
        dist = next;
    }
    return dist[dst] === INF ? -1 : dist[dst];
}

Complexity

Time O(K · E)Space O(N)

K is the stop limit k, E the number of flights and N the number of cities. Each of the k + 1 rounds scans every flight once. dist and next each hold one price per city.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Depth-first search over all trips with at most k + 1 flights; keep the cheapest that lands on dst	O(N^(K + 1))	O(N + E)
Optimal	Relax every flight once per round for k + 1 rounds; each round reads last round's prices from a copy	O(K · E)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“cheapest price”Each flight adds a price, so the total is a sum along the trip. This is a weighted shortest-path question.
“at most k stops”A limit on the number of flights. Dijkstra can't count flights, so the limit needs rounds.
“return -1 if no such trip”Some cities stay ∞ after the rounds, so they must be checked before returning.

weighted flights+at most k + 1 flights+one round per flight, reading from a copy→Shortest Paths (weighted): Bellman-Ford with an edge limit

Dijkstra fits 'cheapest price' but not 'at most k stops': it keeps only the cheapest trip to each city, even when that trip uses too many flights. This question is the anchor of the Bellman-Ford sub-pattern. The rule that decides validity is a flight count, not a visited set or a cost check, so the rounds are what make the limit exact. The copy per round is the detail that must not be skipped.

Don't make this mistake

Plain Dijkstra that ignores the stop count

✗ // priority_queue of (cost, city): pop the cheapest city, relax its flights, stop when dst is popped

✓ for (int round = 0; round <= k; round++) { /* copy dist, relax every flight */ }

Dijkstra keeps one cheapest trip per city, even when it uses too many flights. On example 1 with k = 1 it settles city 2 at 200 (2 flights), then city 3 at 400 through it (3 flights). It returns 400, but the answer is 700. This is the pattern-confusion trap: the stop limit needs rounds, not a heap.

Relaxing in place

✗ dist[v] = dist[u] + price; // writes straight into dist, so the same round reads it again

✓ next[v] = dist[u] + price; // writes into the copy; reads still come from dist

One in-place round on example 1 already gives dist = [0, 100, 200, 400]. Flight 1 → 2 reads the 100 written a moment earlier, and flight 2 → 3 reads the 200. City 3 gets 400 in one round with three flights. With k = 1 the function returns 400 instead of 700.

Off by one on k

✗ for (int round = 0; round < k; round++) { ... }

✓ for (int round = 0; round <= k; round++) { ... }

k stops means k + 1 flights, so we need k + 1 rounds. On example 3 (k = 0) the wrong loop runs no rounds at all. dist[2] stays ∞, and the function returns -1 instead of 500.

Relaxing from a city that cannot be reached yet

✗ if (dist[u] + price < next[v]) next[v] = dist[u] + price; // INF = INT_MAX

✓ if (dist[u] != INF && dist[u] + price < next[v]) next[v] = dist[u] + price;

INT_MAX + price overflows. In C++ that is undefined behaviour, and in practice it wraps to a negative number. An unreachable city then looks cheaper than everything, so a fake price gets into the answer. Check dist[u] != INF first.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Shortest Paths (Weighted) translate into production architectures and low-level memory mechanics.

LLD Architecture