Cheapest Flights K Stops LeetCode 787

LeetCode 787 — Cheapest Flights Within K Stops — gives you n cities connected by flights, each with a price. You must find the cheapest price from a source city src to a destination city dst using at most k stops. A stop is an intermediate city, so at most k stops means at most k+1 edges. If no such route exists, return -1.

Each flight is a tuple (from, to, price) representing a directed edge with a positive cost. The graph is directed — a flight from city A to city B does not imply a return flight. Multiple flights between the same pair of cities can exist at different prices.

The key constraint that makes this problem interesting is the k stops limit. Without it, any standard shortest path algorithm (Dijkstra, Bellman-Ford) would work directly. With it, you must track not just the cheapest cost to reach a city, but also how many edges were used to get there.

Dijkstra's algorithm greedily settles nodes: once a node is popped from the min-heap with distance d, that distance is declared final and the node is never revisited. This works perfectly when the only goal is minimum cost — a settled node truly has its optimal cost.

But with a k stops constraint, a node being "settled" at minimum cost does not mean it has been reached via the minimum number of edges. A cheaper path might use more stops, and a path within the stop limit might cost more. Once Dijkstra settles a node, it will never update that node even if a later path reaches it within k stops at a slightly higher cost.

To use Dijkstra-style thinking here, you must track state as (node, stops_used) rather than just (node). This effectively expands the graph to n*(k+1) states — workable, but Bellman-Ford with k rounds is simpler and more natural for this constraint.

Standard Bellman-Ford runs V-1 rounds to relax all edges until no improvement is found. The key insight for this problem: after i rounds of relaxation, dist[node] represents the cheapest cost to reach that node using at most i edges. So running exactly k+1 rounds gives us the cheapest price using at most k+1 edges — exactly what we need.

In each round, iterate over all flights (u, v, price). If dist[u] + price < dist[v], update dist[v]. After k+1 rounds, dist[dst] holds the answer. Initialize dist[src] = 0 and all others to infinity.

The critical implementation detail: you must copy the distances array before each round and use the previous round's values for updates. This prevents updates within a single round from cascading into the same round, which would allow more than i edges to be used in round i.

Without copying the distances array before each round, an update in the current round can immediately be used by another edge in the same round. For example, in round 1 you might update dist[B] via edge A→B, then immediately update dist[C] via edge B→C — effectively using two edges in a single round. This would allow more than k+1 edges total.

By copying dist to prev_dist at the start of each round and reading from prev_dist while writing to dist, you ensure that round i only uses paths that were valid after round i-1. The update to dist[B] in round i is not visible to other edges in round i — only in round i+1.

This distinction is the most common bug in implementations of this approach. Without the copy, the algorithm may return a cheaper price that uses more than k stops, giving a wrong answer on test cases designed to catch this.

An alternative approach uses BFS level by level, where each level represents one additional stop. Start with a queue containing just (src, 0) — the source city with cost 0. At each level, expand all cities in the current frontier by one more flight. Track the best known cost to reach each city.

Prune aggressively: if the cost to reach a city is already worse than the best known cost to dst, skip it. Also skip if we have exceeded k stops. At most k+1 levels are processed. This approach is more intuitive as "explore one flight at a time" and can be faster in practice due to pruning.

The BFS approach uses a cost array best[] where best[city] tracks the minimum cost seen so far to reach that city at any number of stops. Pruning paths that already exceed best[dst] can dramatically reduce the search space when a cheap direct or near-direct flight exists.

In Python (Bellman-Ford), initialize prices = [float('inf')] * n with prices[src] = 0. Loop k+1 times: copy tmp = prices[:] at the start. For each (u, v, price) in flights: if tmp[u] != inf and tmp[u] + price < prices[v], set prices[v] = tmp[u] + price. Return prices[dst] if it is not infinity else -1. Time: O(k * E), Space: O(V).

In Java (Bellman-Ford), use int[] prices = new int[n] initialized to Integer.MAX_VALUE / 2 (to avoid overflow on addition). Set prices[src] = 0. Loop k+1 times: copy int[] tmp = prices.clone(). For each int[] flight in flights: if tmp[flight[0]] != MAX/2 and tmp[flight[0]] + flight[2] < prices[flight[1]], update prices[flight[1]]. Return prices[dst] >= MAX/2 ? -1 : prices[dst].

Both implementations are O(k * |flights|) time and O(n) space — clean, interview-ready, and correct. The BFS version has the same worst-case complexity but can be faster in practice. Choose Bellman-Ford for simplicity and BFS if you want to demonstrate breadth of knowledge.

Cheapest Flights Within K Stops belongs to the "constrained shortest path" family — problems where you minimize cost subject to a secondary constraint. Network Delay Time (LC 743) is the same graph structure without the stop limit, solved with pure Dijkstra. Shortest Path in Binary Matrix (LC 1091) is unweighted shortest path with a grid constraint.

Swim in Rising Water (LC 778) minimizes the maximum edge weight on a path — a min-max variant. These problems all share the adjacency list plus priority queue or BFS framework, but each adds a twist that requires adapting the core algorithm. The stop constraint in LC 787 is the canonical example of why state expansion or round-limited relaxation is needed.

For broader interview preparation, study the full constrained graph search family: k stops (LC 787), time-limited path (variations of Dijkstra with expiry), minimum effort (LC 1631), and path with minimum maximum edge (LC 1631, 778). Each one teaches a different adaptation technique applicable across graph problems.