787. Cheapest Flights Within K Stops (Medium)

Problem

Given n cities and flights flights[i] = [fromᵢ, toᵢ, priceᵢ], return the cheapest price from src to dst using at most k stops (intermediate cities), or -1 if impossible.

Example

n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1 → 700
Same setup, k = 0 → -1

LeetCode 787 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, DFS with memo

DFS all paths from src, prune with cost; memoize by (city, remaining_stops).

from collections import defaultdict
from functools import lru_cache

def find_cheapest_price(n, flights, src, dst, k):
    graph = defaultdict(list)                          # L1: build adjacency list, O(E)
    for u, v, w in flights:
        graph[u].append((v, w))                        # L2: O(1) per edge

    @lru_cache(maxsize=None)
    def dfs(city, stops_left):                         # L3: memoized over V*K states
        if city == dst:
            return 0
        if stops_left < 0:
            return float('inf')
        best = float('inf')
        for nb, cost in graph[city]:                   # L4: iterate neighbors, O(deg)
            best = min(best, cost + dfs(nb, stops_left - 1))  # L5: recurse, O(1) if cached
        return best

    result = dfs(src, k + 1)                           # L6: O(V*K*avg_deg) total
    return -1 if result == float('inf') else result

function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
    const graph = new Map<number, [number, number][]>();
    for (const [u, v, w] of flights) {                // L1: build adjacency list, O(E)
        if (!graph.has(u)) graph.set(u, []);
        graph.get(u)!.push([v, w]);                   // L2: O(1) per edge
    }

    const memo = new Map<string, number>();

    function dfs(city: number, stopsLeft: number): number {  // L3: memoized over V*K states
        if (city === dst) return 0;
        if (stopsLeft < 0) return Infinity;
        const key = `${city},${stopsLeft}`;
        if (memo.has(key)) return memo.get(key)!;
        let best = Infinity;
        for (const [nb, cost] of (graph.get(city) ?? [])) {  // L4: iterate neighbors, O(deg)
            const sub = dfs(nb, stopsLeft - 1);
            if (sub !== Infinity) best = Math.min(best, cost + sub);  // L5: recurse, O(1) if cached
        }
        memo.set(key, best);
        return best;
    }

    const result = dfs(src, k + 1);                   // L6: O(V*K*avg_deg) total
    return result === Infinity ? -1 : result;
}

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
    graph := make(map[int][][2]int)
    for _, f := range flights {                        // L1: build adjacency list, O(E)
        u, v, w := f[0], f[1], f[2]
        graph[u] = append(graph[u], [2]int{v, w})     // L2: O(1) per edge
    }
    memo := make(map[[2]int]int)
    var dfs func(city, stopsLeft int) int
    dfs = func(city, stopsLeft int) int {              // L3: memoized over V*K states
        if city == dst { return 0 }
        if stopsLeft < 0 { return 1<<31 - 1 }
        key := [2]int{city, stopsLeft}
        if v, ok := memo[key]; ok { return v }
        best := 1<<31 - 1
        for _, edge := range graph[city] {             // L4: iterate neighbors, O(deg)
            nb, cost := edge[0], edge[1]
            sub := dfs(nb, stopsLeft-1)                // L5: recurse, O(1) if cached
            if sub != 1<<31-1 && cost+sub < best { best = cost + sub }
        }
        memo[key] = best
        return best
    }
    result := dfs(src, k+1)                           // L6: O(V*K*avg_deg) total
    if result == 1<<31-1 { return -1 }
    return result
}

final class Solution {
    func findCheapestPrice(_ n: Int, _ flights: [[Int]], _ src: Int, _ dst: Int, _ k: Int) -> Int {
        var graph = Array(repeating: [(Int,Int)](), count:n); for flight in flights { graph[flight[0]].append((flight[1],flight[2])) }; let infinity=Int.max/4; var memo=Array(repeating:Array(repeating:-2,count:k+2),count:n)
        func solve(_ node:Int,_ edges:Int)->Int { if node==dst { return 0 }; if edges==0 { return infinity }; if memo[node][edges] != -2 { return memo[node][edges] }; var best=infinity; for (next,cost) in graph[node] { let suffix=solve(next,edges-1); if suffix<infinity { best=min(best,cost+suffix) } }; memo[node][edges]=best; return best }
        let answer=solve(src,k+1); return answer==infinity ? -1 : answer
    }
}

Where the time goes, line by line

Variables: V = n (cities), E = len(flights), K = the stops parameter.

Line	Per-call cost	Times executed	Contribution
L1-L2 (build graph)	$O(1)$ per edge	E	$O(E)$
L3 (unique memoized states)	-	V * (K+1) distinct	-
L4 (neighbor iteration)	$O(deg(city)$ )	once per state	$O(E * K)$ total
L5 (recurse/lookup)	$O(1)$ amortized (cache hit)	*V K * avg_deg**	*$O(E K)$** ← dominates
L6 (initial call)	$O(V * K * avg_deg)$	1	$O(E * K)$

Each (city, stops_left) pair is computed exactly once; its neighbors are iterated once. Total states: V * (K+1). Each state visits avg_deg neighbors, and sum of degrees = E, so total work is $O(E * K)$ .

Complexity

Time: $O(E * K)$ , driven by L4/L5 (each memoized state visits its neighbors once).
Space: $O(E + V * K)$ for the graph and memo cache.

Approach 2: Modified Dijkstra with (cost, node, stops_remaining)

Dijkstra-ish with a third dimension for hops left; prune entries that exhaust hops before reaching dst.

import heapq
from collections import defaultdict

def find_cheapest_price(n, flights, src, dst, k):
    graph = defaultdict(list)                          # L1: build adjacency list, O(E)
    for u, v, w in flights:
        graph[u].append((v, w))                        # L2: O(1) per edge
    # (cost, city, stops_left)
    heap = [(0, src, k + 1)]                           # L3: seed heap, O(1)
    while heap:                                        # L4: outer loop, up to E*K pushes
        cost, city, stops = heapq.heappop(heap)        # L5: O(log(heap_size))
        if city == dst:
            return cost
        if stops > 0:
            for nb, w in graph[city]:                  # L6: iterate neighbors
                heapq.heappush(heap, (cost + w, nb, stops - 1))  # L7: O(log(heap_size))
    return -1

function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
    const graph = new Map<number, [number, number][]>();
    for (const [u, v, w] of flights) {                // L1: build adjacency list, O(E)
        if (!graph.has(u)) graph.set(u, []);
        graph.get(u)!.push([v, w]);                   // L2: O(1) per edge
    }
    const heap = new MinHeap();
    heap.push([0, src, k + 1]);                       // L3: seed heap, O(1)
    while (heap.size > 0) {                           // L4: outer loop, up to E*K pushes
        const [cost, city, stops] = heap.pop();       // L5: O(log(heap_size))
        if (city === dst) return cost;
        if (stops > 0) {
            for (const [nb, w] of (graph.get(city) ?? [])) {  // L6: iterate neighbors
                heap.push([cost + w, nb, stops - 1]);  // L7: O(log(heap_size))
            }
        }
    }
    return -1;
}

// See 787-cheapest-flights-within-k-stops-approach2.go for the full runnable program.
// Core function uses container/heap with Item787{cost, city, stops int}.
func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
    graph := make(map[int][][2]int)
    for _, f := range flights {                         // L1: build adjacency list, O(E)
        u, v, w := f[0], f[1], f[2]
        graph[u] = append(graph[u], [2]int{v, w})      // L2: O(1) per edge
    }
    h := &MinHeap787{{cost: 0, city: src, stops: k+1}}
    heap.Init(h)                                        // L3: seed heap, O(1)
    for h.Len() > 0 {                                   // L4: outer loop, up to E*K pushes
        item := heap.Pop(h).(Item787)
        cost, city, stops := item.cost, item.city, item.stops  // L5: O(log(heap_size))
        if city == dst { return cost }
        if stops > 0 {
            for _, edge := range graph[city] {          // L6: iterate neighbors
                nb, w := edge[0], edge[1]
                heap.Push(h, Item787{cost: cost+w, city: nb, stops: stops-1})  // L7
            }
        }
    }
    return -1
}

Where the time goes, line by line

Variables: V = n (cities), E = len(flights), K = the stops parameter.

Line	Per-call cost	Times executed	Contribution
L1-L2 (build graph)	$O(1)$ per edge	E	$O(E)$
L3 (init heap)	$O(1)$	1	$O(1)$
L4 (loop)	$O(1)$	up to E*K	$O(E*K)$
L5 (pop)	*$O(log(EK)$ )**	*up to EK**	*$O(EKlog(EK)$ )** ← dominates
L6 (neighbors)	$O(deg)$	once per pop	$O(E*K)$ total
L7 (push)	$O(log(E*K)$ )	up to E*K	$O(EKlog(E*K)$ )

The heap can hold up to $O(E*K)$ entries because each edge can be pushed once per remaining-stop level. Each push/pop is $O(log(E*K)$ ). Unlike classic Dijkstra, this does not deduplicate by (node, stops) so the same city may be popped multiple times.

Complexity

Time: $O(E * K * log(E * K)$ ), driven by L5/L7 (heap operations on a queue that can grow to E*K entries).
Space: $O(E + V * K)$ for the graph and heap.

Works but may re-expand nodes with fewer stops and higher cost.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func findCheapestPrice(_ n: Int, _ flights: [[Int]], _ src: Int, _ dst: Int, _ k: Int) -> Int {
        var graph=Array(repeating:[(Int,Int)](),count:n); for flight in flights { graph[flight[0]].append((flight[1],flight[2])) }; let infinity=Int.max/4; var distance=Array(repeating:Array(repeating:infinity,count:n),count:k+2); distance[0][src]=0
        var queue=BinaryHeap<(Int,Int,Int)>(hasHigherPriority:{$0.0<$1.0}); queue.insert((0,src,0))
        while let (cost,node,edges)=queue.removeRoot() { if node==dst { return cost }; if edges==k+1 || cost != distance[edges][node] { continue }; for (next,price) in graph[node] { let candidate=cost+price; if candidate<distance[edges+1][next] { distance[edges+1][next]=candidate; queue.insert((candidate,next,edges+1)) } } }; return -1
    }
}

Approach 3: Bellman-Ford with hop limit (canonical)

Run Bellman-Ford exactly k + 1 iterations (each iteration = one more hop allowed). Snapshot distances each round to avoid using this-round relaxations.

def find_cheapest_price(n, flights, src, dst, k):
    INF = float('inf')
    dist = [INF] * n                                   # L1: init distances, O(V)
    dist[src] = 0                                      # L2: source costs zero
    for _ in range(k + 1):                             # L3: outer loop, K+1 rounds
        new_dist = dist.copy()                         # L4: snapshot, O(V)
        for u, v, w in flights:                        # L5: scan all edges, O(E)
            if dist[u] != INF and dist[u] + w < new_dist[v]:  # L6: relax if better
                new_dist[v] = dist[u] + w              # L7: O(1) update
        dist = new_dist                                # L8: commit snapshot
    return -1 if dist[dst] == INF else dist[dst]       # L9: O(1) lookup

function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
    const INF = Infinity;
    let dist = new Array(n).fill(INF);                 // L1: init distances, O(V)
    dist[src] = 0;                                     // L2: source costs zero
    for (let round = 0; round <= k; round++) {         // L3: outer loop, K+1 rounds
        const newDist = [...dist];                     // L4: snapshot, O(V)
        for (const [u, v, w] of flights) {             // L5: scan all edges, O(E)
            if (dist[u] !== INF && dist[u] + w < newDist[v]) {  // L6: relax if better
                newDist[v] = dist[u] + w;              // L7: O(1) update
            }
        }
        dist = newDist;                                // L8: commit snapshot
    }
    return dist[dst] === INF ? -1 : dist[dst];        // L9: O(1) lookup
}

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
    const INF = 1<<31 - 1
    dist := make([]int, n)                              // L1: init distances, O(V)
    for i := range dist { dist[i] = INF }
    dist[src] = 0                                       // L2: source costs zero
    for i := 0; i <= k; i++ {                          // L3: outer loop, K+1 rounds
        newDist := make([]int, n)
        copy(newDist, dist)                             // L4: snapshot, O(V)
        for _, f := range flights {                     // L5: scan all edges, O(E)
            u, v, w := f[0], f[1], f[2]
            if dist[u] != INF && dist[u]+w < newDist[v] {  // L6: relax if better
                newDist[v] = dist[u] + w                // L7: O(1) update
            }
        }
        dist = newDist                                  // L8: commit snapshot
    }
    if dist[dst] == INF { return -1 }
    return dist[dst]                                    // L9: O(1) lookup
}

Where the time goes, line by line

Variables: V = n (cities), E = len(flights), K = the stops parameter.

Line	Per-call cost	Times executed	Contribution
L1-L2 (init)	$O(V)$	1	$O(V)$
L3 (outer loop)	$O(1)$	K+1	$O(K)$
L4 (snapshot)	$O(V)$	K+1	$O(V*K)$
L5-L7 (edge scan + relax)	$O(1)$ per edge	E per round, K+1 rounds	*$O(EK)$** ← dominates
L8-L9 (commit + lookup)	$O(1)$	K+1	$O(K)$

The double loop is exactly (K+1) rounds times E edges. The snapshot at L4 is the critical correctness detail: it prevents a chain u -> v -> x from consuming two hops in a single round.

Complexity

Time: $O(K * E)$ , driven by L5-L7 (the inner edge scan across all K+1 rounds).
Space: $O(V)$ for two distance arrays (dist and new_dist).

Why the snapshot matters

Without copying, a flight u -> v relaxed in iteration i could be immediately used by v -> x in the same iteration, that’s two hops in one “hop budget” slot, corrupting the answer.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func findCheapestPrice(_ n: Int, _ flights: [[Int]], _ src: Int, _ dst: Int, _ k: Int) -> Int {
        let infinity=Int.max/4; var cost=Array(repeating:infinity,count:n); cost[src]=0
        for _ in 0...k { var next=cost; for flight in flights where cost[flight[0]]<infinity { next[flight[1]]=min(next[flight[1]],cost[flight[0]]+flight[2]) }; cost=next }
        return cost[dst]==infinity ? -1 : cost[dst]
    }
}

Summary

Approach	Time	Space
DFS + memo	$O(E * K)$	$O(E + V * K)$
Modified Dijkstra	$O(E * K * log(E * K)$ )	$O(E + V * K)$
Bellman-Ford + hop cap	*$O(K E)$**	$O(V)$

Bellman-Ford with a hop cap is the cleanest solution for this shape of problem, the hop count is exactly k + 1 iterations. Same pattern applies to any “at-most-k-edges” shortest-path variant.

Test cases

# Quick smoke tests, paste into a REPL or save as test_787.py and run.
# Uses the canonical implementation (Approach 3: Bellman-Ford with hop limit).

def find_cheapest_price(n, flights, src, dst, k):
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0
    for _ in range(k + 1):
        new_dist = dist.copy()
        for u, v, w in flights:
            if dist[u] != INF and dist[u] + w < new_dist[v]:
                new_dist[v] = dist[u] + w
        dist = new_dist
    return -1 if dist[dst] == INF else dist[dst]

def _run_tests():
    flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
    # Example: k=1 -> 0->1->3 costs 700
    assert find_cheapest_price(4, flights, 0, 3, 1) == 700
    # k=0 means no stops, no direct flight from 0 to 3
    assert find_cheapest_price(4, flights, 0, 3, 0) == -1
    # k=2 -> 0->1->2->3 costs 400
    assert find_cheapest_price(4, flights, 0, 3, 2) == 400
    # Single flight, reachable with 0 stops
    assert find_cheapest_price(2, [[0,1,500]], 0, 1, 0) == 500
    # src == dst -> cost 0
    assert find_cheapest_price(3, [[0,1,100],[1,2,50]], 1, 1, 1) == 0
    # Unreachable destination
    assert find_cheapest_price(3, [[0,1,100]], 0, 2, 5) == -1
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
    const INF = Infinity;
    let dist = new Array(n).fill(INF);
    dist[src] = 0;
    for (let round = 0; round <= k; round++) {
        const newDist = [...dist];
        for (const [u, v, w] of flights) {
            if (dist[u] !== INF && dist[u] + w < newDist[v]) newDist[v] = dist[u] + w;
        }
        dist = newDist;
    }
    return dist[dst] === INF ? -1 : dist[dst];
}

const flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]];
console.assert(findCheapestPrice(4, flights, 0, 3, 1) === 700);
console.assert(findCheapestPrice(4, flights, 0, 3, 0) === -1);
console.assert(findCheapestPrice(4, flights, 0, 3, 2) === 400);
console.assert(findCheapestPrice(2, [[0,1,500]], 0, 1, 0) === 500);
console.assert(findCheapestPrice(3, [[0,1,100],[1,2,50]], 1, 1, 1) === 0);
console.assert(findCheapestPrice(3, [[0,1,100]], 0, 2, 5) === -1);
console.log("all tests pass");

Graphs, Bellman-Ford; hop-limited shortest path

Bellman-Ford, repeated-relaxation tactics for shortest paths with negative edges, bounded stops, or layered constraints.
Shortest Paths, path-cost tactics for finding minimum distance, time, risk, or transformation count through a graph.

787. Cheapest Flights Within K Stops (Medium)

Problem

Try it yourself

Approach 1: Brute force, DFS with memo

Approach 2: Modified Dijkstra with (cost, node, stops_remaining)

Approach 3: Bellman-Ford with hop limit (canonical)

Why the snapshot matters

Summary

Test cases

Related data structures

Related concepts