Skip to content

Volume ITechnology

4.21.6 — Cheapest Flights Within K Stops ​

LeetCode 787 · Medium

The problem ​

Find the cheapest route from src to dst using at most k stops — that is, at most k + 1 flights. Return -1 if there is none.

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     (0 → 1 → 3, one stop)

In plain English, you want to fly from a starting city to a destination city as cheaply as possible. But there's a catch: you get airsick easily, so you absolutely refuse to take a route with more than k layovers (meaning k stops in the middle, or k+1 total flight legs). Find the cheapest route satisfying this condition. If none exists, return -1.

The route 0 → 1 → 2 → 3 costs only 500, but it uses two stops and is not allowed.

Why Dijkstra gives the wrong answer ​

This is the heart of the problem, so we are precise about it.

Dijkstra finalises a node the first time it pops, on the grounds that no cheaper route can exist. With a hop limit that reasoning collapses:

A cheap route to a node may use too many hops to be extended further, while a more expensive route with fewer hops is the one you need.

A picture to hold in mind ​

Imagine a travel agent looking for tickets. The agent says, "Good news! I got you to Chicago for just $50!" You say, "Great, from Chicago we can go to New York." The agent replies, "Ah, sorry, the $50 ticket took 8 layovers, and you said max 2 layovers. We can't go any further." You ask, "Well, did you see any slightly more expensive flights to Chicago that only had 1 layover?" The agent says, "I stopped looking the moment I found the $50 one!" That travel agent is Dijkstra. Dijkstra only cares about finding the absolute cheapest path to a node and immediately stops searching for other paths to that node. When you introduce a secondary constraint (like max layovers), Dijkstra's single-minded greediness breaks.

In the example, Dijkstra reaches node 2 cheaply via 0 → 1 → 2 for 200, then finalises it. But that route has already used two flights, so continuing to 3 needs a third and exceeds the limit. Meanwhile node 1 at cost 100 with one flight used is the route that actually works.

The lesson generalises: Dijkstra's finalisation is only valid when cost is the only thing that matters. Add a second constraint — hop count, fuel, time window — and a node's "best" state is no longer a single number, so a single finalised distance is not enough.

Two ways out.

Solution 1 — Bellman-Ford, and it fits perfectly ​

Bellman-Ford relaxes every edge, repeatedly. After i rounds, it knows the cheapest route using at most i edges.

That is exactly the constraint here. Run it k + 1 times and you have the cheapest route using at most k + 1 flights. The hop limit, which broke Dijkstra, is the very thing Bellman-Ford counts.

python
class Solution:
    def findCheapestPrice(self, n, flights, src, dst, k) -> int:
        INF = float('inf')  # (1)
        cost = [INF] * n  # (2)
        cost[src] = 0  # (3)

        for _ in range(k + 1):                 # (4) at most k+1 flights
            snapshot = cost[:]                 # (5) ← the critical line
            for u, v, w in flights:  # (6)
                if snapshot[u] + w < cost[v]:  # (7)
                    cost[v] = snapshot[u] + w

        return cost[dst] if cost[dst] != INF else -1  # (8)
ts
function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
  const INF = Infinity;  // (1)
  let cost = new Array(n).fill(INF);  // (2)
  cost[src] = 0;  // (3)

  for (let round = 0; round <= k; round++) {  // (4)
    const snapshot = [...cost];  // (5)
    for (const [u, v, w] of flights) {  // (6)
      if (snapshot[u] + w < cost[v]) cost[v] = snapshot[u] + w;  // (7)
    }
  }

  return cost[dst] === INF ? -1 : cost[dst];  // (8)
}

snapshot = cost[:] is the line the whole solution depends on.

Without it, a single round could chain several flights: relaxing 0 → 1 updates cost[1], and then relaxing 1 → 2 in the same round uses that fresh value, so two flights were taken in one round. The hop count becomes meaningless.

Copying the array first means every relaxation in a round reads the state from the end of the previous round, so exactly one flight is added per round. That is the difference between "at most i edges" and "any number of edges", and it is why standard Bellman-Ford — which does not snapshot — cannot answer this question directly.

O(k \times E) time, O(n) space. Short, and easy to defend.

Line by line ​

This is the Bellman-Ford algorithm, limited to k + 1 rounds. After round r, cost[v] holds the cheapest price to reach v using at most r flights.

(1) Infinity stands for "not reachable yet".

(2) Every city starts unreachable,

(3) except the starting city, which costs nothing to be at.

(4) k stops means at most k + 1 flights, so run exactly k + 1 rounds.

(5) Copy the prices from the end of the previous round. This is the line that makes the stop limit work. Inside one round, every update must use prices from before the round. Otherwise a city updated early in this round could pass its new price on to another city in the same round, which would quietly use two flights in one round, and break the limit.

(6) Try every flight.

(7) If flying from u to v is cheaper than the best known price for v, using u's price from the snapshot, take it.

(8) The cheapest price to the destination, or −1 if it was never reached within k + 1 flights.

Edge cases ​

  • k = 0. Only direct flights count. One round.
  • The destination is unreachable within k stops, even if a longer route exists. The answer is −1.
  • The cheapest route needs more stops than allowed. A dearer route with fewer stops wins. That is exactly what the round limit enforces.

Solution 2 — BFS by levels ​

Walk outward one flight at a time, keeping the cheapest known cost to each node.

python
from collections import deque

def findCheapestPrice(self, n, flights, src, dst, k):
    adj = defaultdict(list)
    for u, v, w in flights:
        adj[u].append((v, w))

    best = [float('inf')] * n
    best[src] = 0
    queue = deque([(src, 0)])
    stops = 0

    while queue and stops <= k:
        for _ in range(len(queue)):            # one level = one flight
            node, cost = queue.popleft()
            for nei, w in adj[node]:
                if cost + w < best[nei]:       # only continue if we improved
                    best[nei] = cost + w
                    queue.append((nei, cost + w))
        stops += 1

    return best[dst] if best[dst] != float('inf') else -1

The level structure counts the flights, and pruning on cost + w < best[nei] stops the queue exploding. It is the same shape as every level-order BFS in this book.

Solution 3 — Dijkstra with the state extended ​

Dijkstra can be rescued by changing what a "node" means. Make the state (node, flights used) rather than just node, and track the best cost for each combination.

python
heap = [(0, src, 0)]        # (cost, node, flights used)

Now finalising is safe again, because two routes to the same airport with different flight counts are genuinely different states.

O(E \cdot k \log(V \cdot k)) — more code and more memory than Bellman-Ford. But the idea behind it is the important one:

When a second constraint breaks a graph algorithm, put the constraint into the state.

That move fixes fuel limits, time windows, "at most two refuels", and a large family of DP-on-graph problems. It is the same idea as adding a dimension to a DP table in 4.24.

Which to write ​

Bellman-Ford. It is eight lines, the hop limit is native to it, and the snapshot is easy to explain. Mention the other two and say why you chose this one.

Complexity ​

O(k \times E) time, O(n) space.

Where this goes next ​

  • Bellman-Ford in general — run it V − 1 rounds for shortest paths with negative weights. A further round that still improves something means a negative cycle, since no simple path has more than V − 1 edges. That is how negative cycles are detected.
  • Path with Maximum Probability, Minimum Cost to Reach Destination in Time — the extended-state idea.
  • Real routing — the distance-vector protocols behind RIP are Bellman-Ford, and their count-to-infinity problem is a direct consequence of it. Chapter 5.3.2.

What the interviewer will push on ​

"Why not Dijkstra?" A cheaper route may use too many hops. Give the concrete example from the problem statement.

"Why does Bellman-Ford fit?" After i rounds it knows the cheapest route using at most i edges, which is exactly the constraint.

"Why the snapshot?" Without it, one round can chain several flights and the hop count is meaningless. This is the question that separates people who understand the code from people who copied it.

"Could you still use Dijkstra?" Yes, with (node, flights used) as the state.

"How does Bellman-Ford detect a negative cycle?" An improvement on the V-th round.

One thing to volunteer: state the general rule. "A second constraint breaks Dijkstra's finalisation, so either count the constraint in rounds — Bellman-Ford — or fold it into the state." That sentence covers a whole family of problems.

Next: 4.22 is the chapter most people find hardest, so it is built from the ground up — what makes a problem dynamic programming rather than greedy, the five questions that produce the recurrence, and the four forms the same solution can take.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet