How do you approach Cheapest Flights Within K Stops?

Plain Dijkstra doesn't directly handle the 'at most k stops' constraint - a longer path with fewer stops may be the only valid one.

What is the time complexity of Cheapest Flights Within K Stops?

Time complexity: O((k + 1) * E). Space complexity: O(n).

What are common mistakes on Cheapest Flights Within K Stops?

Building the adjacency list in one direction on an undirected graph. Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest. Ignoring self-loops and parallel edges when the constraints allow them.

gitGood.dev

← Back to problems

Cheapest Flights Within K Stops

HardAlgorithms

Description

There are `n` cities connected by some number of flights. You are given an array `flights` where `flights[i] = [from_i, to_i, price_i]` indicates that there is a flight from city `from_i` to city `to_i` with cost `price_i`. You are also given three integers `src`, `dst`, and `k`. Return **the cheapest price** from `src` to `dst` with at most `k` stops. If there is no such route, return `-1`. A "stop" is an intermediate city - so at most `k` stops means at most `k + 1` edges.

Example 1

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1

Output: 700

Explanation: 0 → 1 → 3 costs 100 + 600 = 700. The cheaper 0 → 1 → 2 → 3 (400) uses 2 stops, exceeding k = 1.

Example 2

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1

Output: 200

Example 3

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0

Output: 500

Constraints

- 1 <= n <= 100 - 0 <= flights.length <= (n * (n - 1) / 2) - flights[i].length == 3 - 0 <= from_i, to_i < n - from_i != to_i - 1 <= price_i <= 10^4 - 0 <= src, dst, k < n - src != dst

Cheapest Flights Within K Stops: approach, complexity and pitfalls

A hard graphs problem, graded against 5 test cases (2 of them hidden).

The pattern: Graphs

Nodes and edges - traversal, connectivity, cycles, and shortest paths.

Reach for it when you see: Explicit edges, a grid treated as a graph, or dependencies between items.

More Graphsproblems →

If you are stuck

Show the 3-step hint ladder

Plain Dijkstra doesn't directly handle the 'at most k stops' constraint - a longer path with fewer stops may be the only valid one.
Bellman-Ford-style: iterate k+1 times, each iteration relaxing every edge using *last iteration's* costs (snapshot).
Alternative: Dijkstra where the state is (city, stopsUsed) and we keep going only if stops <= k.

The optimal approach

Show the approach: k+1 Rounds of Bellman-Ford

Let `cost[v]` = current best cost to reach v with at most `r` edges. Initialise `cost[src] = 0`, everything else infinity.

Repeat `k + 1` times: build a fresh `next` from a copy of `cost`, then for every edge `(u, v, w)` set `next[v] = min(next[v], cost[u] + w)`. Crucially we read from the *previous* round's snapshot, otherwise a single edge could be traversed multiple times within one round.

After `k + 1` rounds, `cost[dst]` is the answer (or `-1` if still infinity).

Time: O((k + 1) * E)
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Graphs mistakes

These apply to the pattern as a whole, not just this problem.

Building the adjacency list in one direction on an undirected graph.
Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest.
Ignoring self-loops and parallel edges when the constraints allow them.