LeetCode · #787

Cheapest Flights Within K Stops Solution

Find the minimum cost from src to dst using at most k stops. The step limit is the key twist: the cheapest unrestricted route might use too many edges.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #787

🏗️

Pattern

Bellman-Ford with step limit

A stop is an intermediate city, so a route with at most k stops can use at most k + 1 flight edges. We want the cheapest such route, or -1 if none exists.

Example

Input:  n = 4
        flights = [[0,1,100],[1,2,100],[2,3,100],[0,2,500]]
        src = 0, dst = 3, k = 1
Output: 600
// 0 → 2 → 3 is valid (1 stop) and costs 600.
// 0 → 1 → 2 → 3 costs 300 but uses 2 stops, so it is invalid.

Section Two · Approach 1

DFS Over All Valid Routes — Exponential

We could recursively try every outgoing flight, tracking current cost and how many edges remain. Whenever we hit dst within the limit, update the answer.

Why it works

Enumerating every route with at most k + 1 edges guarantees we eventually see the cheapest valid one.

Problem: The branching factor can be huge, and many partial routes overlap. This is exactly what Bellman-Ford is good at: shortest paths with a bounded number of edges. We only need k + 1 relaxation passes, not n - 1.

Section Three · Approach 2

Bellman-Ford Limited to K+1 Passes — O((K+1) · E)

Classic Bellman-Ford says that after i passes, we know the cheapest costs using at most i edges. So for this problem, we only need k + 1 passes. The subtle part is that each pass must read from the previous pass's distances, not the ones being updated right now.

💡 Mental model: Think of pass 1 as allowing one flight, pass 2 as allowing two flights, and so on. Each pass unlocks one more edge in the route budget. If you update the same array in-place, one pass can accidentally chain two new edges together and violate the stop limit.

Initialize dist[src] = 0; all others are infinity.
Repeat exactly k + 1 times.
At the start of each pass, clone the previous dist array into next.
Relax every flight u → v using the old dist[u].
After the pass, replace dist with next.

Recognition signal:

“Cheapest / minimum cost with at most K stops / K edges / K moves” usually means Bellman-Ford by number of edges, or a state-augmented Dijkstra.
Bellman-Ford is often the cleanest interview answer here.

Section Four · Trace

Visual Walkthrough

Trace src=0, dst=3, k=1.

Cheapest Flights — limited Bellman-Ford passes

Section Five · Implementation

Code — Java & Python

Java — Bellman-Ford with cloned pass state

import java.util.*;

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

        for (int pass = 0; pass <= k; pass++) {
            int[] next = dist.clone();
            for (int[] flight : flights) {
                int u = flight[0], v = flight[1], price = flight[2];
                if (dist[u] == INF) continue;
                next[v] = Math.min(next[v], dist[u] + price);
            }
            dist = next;
        }

        return dist[dst] == INF ? -1 : dist[dst];
    }
}

Python — K+1 relaxations

class Solution:
    def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
        INF = 10**15
        dist = [INF] * n
        dist[src] = 0

        for _ in range(k + 1):
            nxt = dist[:]
            for u, v, price in flights:
                if dist[u] == INF:
                    continue
                if dist[u] + price < nxt[v]:
                    nxt[v] = dist[u] + price
            dist = nxt

        return -1 if dist[dst] == INF else dist[dst]

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
DFS route enumeration	Exponential	O(k) recursion	Explores too many repeated route prefixes.
Bellman-Ford ← optimal fit	O((K + 1) · E)	O(V)	Exactly matches the “at most K stops” constraint by limiting edge count.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Expected behavior	Why it matters
No valid route within stop limit	Return `-1`	The cheapest unrestricted route may still be invalid.
`k = 0`	Allow only direct flights	That means exactly one Bellman-Ford pass.
Cheaper route with too many stops	Ignore it	The constraint is part of the optimization problem.
Unreachable intermediate city	Skip its outgoing relaxations	Guard against adding to infinity.
In-place updates per pass	Wrong answer	One pass would accidentally use more than one newly unlocked edge.

⚠ Common Mistake: Updating dist in-place during a pass. That breaks the “at most i edges after i passes” invariant. Always write into a cloned array for the current pass.

← Back to Shortest Path

LearningTree

LC 787 · Cheapest Flights Within K Stops — Solution & Explanation | DSA Guide