· By John Kavanagh

Cheapest Flights Within K Stops: Keep the Journey Length

An aircraft wing above clouds, seen through a passenger window.
Image by Samuel T, licensed from Unsplash.

The cheapest way to reach a city can be a useless way to reach your destination. If it consumes the entire stop allowance, arriving cheaply doesn't leave you much to work with.

That is the wrinkle in Cheapest Flights Within K Stops on LeetCode. Flights are directed connections with prices. Given a starting city, a destination, and a maximum number of intermediate stops, we need the cheapest permitted journey, or -1 if none exists.

My Network Delay Time article explains why Dijkstra's algorithm can keep one best distance per node when weights are non‑negative. Here a city alone isn't a complete description of our position. We also need to know how many flights we've taken. A cheap ticket is less appealing if it leaves you stranded one connection short.


Count Flights Before Counting Costs

Zero stops means a direct flight. One stop allows two flights. In general, k intermediate stops permit at most k + 1 edges. I write that relationship down before touching the recurrence because a beautifully implemented off‑by‑one error is still an off‑by‑one error.

Consider four flights: 0 → 1 costs 1, 1 → 2 costs 1, 0 → 2 costs 5, and 2 → 3 costs 1. We want to travel from 0 to 3 with at most one stop.

The cheapest arrival at city 2 costs 2, via city 1, but it has already used two flights. It cannot continue to city 3. The more expensive direct arrival at city 2 costs 5 and leaves room for the final flight. The correct total is 6, not 3 and not -1.

If a cost‑first search throws away the arrival costing 5 simply because 2 is cheaper, it loses the valid answer. Neither arrival dominates the other: one has a better price, the other has used fewer flights.


Give Each Row a Precise Meaning

I use a bounded Bellman–Ford approach. Let a row record the cheapest price for reaching each city using at most a particular number of flights. Before taking any flights, the source costs zero and every other city has cost Infinity.

To produce the next row, start with a copy of the previous one. Copying preserves journeys that already use fewer flights. Then consider each connection once: a route to its origin from the previous row, followed by this flight, is a candidate for its destination in the new row.

The key phrase is "from the previous row". Every candidate extends a journey that has already respected the preceding limit. One pass therefore adds at most one flight, regardless of the order in which the input lists the connections.

This is the same state‑selection habit I describe in my dynamic‑programming state guide. Give the stored value a complete sentence before compressing anything. Here that sentence includes both a city and an allowed number of flights, even though only one dimension survives in each array.


Two Arrays are a Correctness Decision

With the small example above, the initial row is [0, Infinity, Infinity, Infinity]. After one pass, it becomes [0, 1, 5, Infinity]. After two passes, it is [0, 1, 2, 6].

Notice the apparently awkward result: the final row records price 2 for city 2, but price 6 for city 3. That is correct. The calculation of city 3 used the preceding row's price 5, not the current row's newly improved 2. Each entry independently describes the best journey within the same edge allowance; the entries aren't a single itinerary.

Updating one shared array in place would allow 0 → 1, 1 → 2, and 2 → 3 to feed into each other during a single pass. The result would depend on input ordering, and the stop limit would quietly disappear. Reversing the edge list might make a test pass, but it wouldn't repair the algorithm.

const findCheapestPrice = (
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number,
): number => {
  let previous: number[] = Array(n).fill(Infinity);
  previous[src] = 0;

  for (let edges = 1; edges <= k + 1; edges++) {
    const next = previous.slice();
    for (const flight of flights) {
      const [from, to, price] = flight as [number, number, number];
      if (previous[from] === Infinity) continue;
      next[to] = Math.min(next[to]!, previous[from]! + price);
    }
    previous = next;
  }

  return previous[dst] === Infinity ? -1 : previous[dst]!;
};

The new array is created inside each pass. Assigning previous = next happens only after every connection has been considered. slice() is therefore part of the reasoning, not just a convenient way to avoid mutation.

Cities use zero‑based labels in this problem. The function accepts LeetCode's promised input shape; the tuple assertion doesn't validate an arbitrary JSON payload. Neither the outer flights array nor its rows are modified.


Why the Recurrence Covers Every Permitted Journey

Assume the previous row contains the correct costs for journeys using at most r - 1 flights. A permitted journey using at most r flights either already fits that smaller allowance, or ends with one final connection.

The copy handles the first case. For the second, remove the final connection: the remaining journey uses at most r - 1 flights, so its best possible price is available in the previous row. Examining every connection considers every possible final step. Taking the minimum keeps the cheapest candidate.

The initial row establishes the claim for zero flights. Repeating the argument k + 1 times gives the required allowance. The source's zero cost remains available because the rows mean "at most", rather than "exactly".

There is no early return when the destination first becomes reachable. A later pass can reveal a cheaper journey within the permitted limit. An optional optimisation could stop when a whole pass makes no improvements, but I have left that out to keep the connection between passes and flight counts visible.


Costs and Alternative Approaches

Let V be the number of cities and E the number of flights. Each pass copies V costs and scans E connections. Including initialisation, the running time is O(V + (k + 1)(V + E)), with O(V) auxiliary space. The two arrays coexist during a pass; we don't retain a full table of every allowance.

The copying cost matters, particularly when there are very few flights. Calling this simply O(kE) would describe the relaxation work but omit part of this implementation. The input list is borrowed rather than rebuilt as an adjacency structure.

A priority queue can also solve the problem if its state includes the number of flights used, with separate best costs for those states. That is a valid extension of Dijkstra's algorithm. I prefer the two‑row solution here because the problem allows at most 100 cities, and enforcing the limit through the loop is easy to inspect.

Prices and permitted journey lengths keep the totals within JavaScript's exact integer range under the stated constraints. This is a simplified route problem: it doesn't model departure times, connection feasibility, baggage charges, or an airline's enthusiasm for additional fees.


Make the Broken Shortcut Observable

My Weighted Graph Comparison Lab prints the small example's rows and deliberately compares them with an in‑place version. The latter returns a price that buys too many flights. It also includes a cost‑first, city‑only search that incorrectly discards the useful expensive arrival.

The working implementation is checked against exhaustive bounded‑walk enumeration on small synthetic graphs. Tests include no route, zero stops, a cheaper route arriving only on the last permitted pass, cycles, and reversed input order. The independent reference is deliberately slow and used only on small inputs.


Wrapping Up

The stop limit changes what "better" means. Price alone cannot decide whether one arrival is more useful than another, so the algorithm must retain the journey‑length information somewhere.

In this version it lives in the pass number. Reading only from the previous row preserves that meaning. My Unique Paths article shows another rolling‑array solution; the useful comparison is which old values each recurrence still needs, rather than whether both examples happen to use arrays.

Downloadable Resource

  • Weighted Graph Comparison Lab

    Use this lab to compare heap‑based shortest paths with stop‑limited flights. Run independent small‑graph checks and inspect stale arrivals, cost rows, and two deliberately broken shortcuts.

    Download ZIP

Want to find out more?

If you need senior hands‑on support with a complex React or Next.js platform, migration, performance issue, or technical SEO problem, send me the context and I'll tell you where I can help.