LeetCode 787: Cheapest Flights Within K Stops

Problem Restatement

We are given n cities labeled from 0 to n - 1.

We are also given a list of directed flights. Each flight is represented as:

[from_city, to_city, price]

We need to find the cheapest price to travel from src to dst using at most k stops.

A stop means an intermediate city between src and dst.

So at most k stops means at most k + 1 flights.

If no such route exists, return -1.

Input and Output

Function shape:

class Solution:
    def findCheapestPrice(
        self,
        n: int,
        flights: list[list[int]],
        src: int,
        dst: int,
        k: int
    ) -> int:
        ...

Examples

Example 1:

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

There are two relevant routes:

At most 1 stop is allowed, so the cheaper valid route is:

0 -> 1 -> 2

The answer is:

200

Example 2:

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

Now no intermediate stop is allowed.

The route 0 -> 1 -> 2 uses one stop, so it is invalid.

The only valid route is:

0 -> 2

The answer is:

500

First Thought: Use Normal Shortest Path

This looks like a shortest path problem.

Each city is a node.

Each flight is a directed weighted edge.

A normal shortest path algorithm would try to minimize total price.

But here we also have a stop limit.

The cheapest path by price may use too many stops.

For example:

0 -> 1 -> 2 -> 3

may be cheaper than:

0 -> 1 -> 3

but if k = 1, then 0 -> 1 -> 2 -> 3 is invalid because it has two stops.

So we need to track both price and number of flights used.

Key Insight

At most k stops means at most k + 1 flights.

This suggests a bounded version of Bellman-Ford.

Bellman-Ford relaxes all edges repeatedly.

After one relaxation round, we know the cheapest prices using at most one flight.

After two rounds, we know the cheapest prices using at most two flights.

After k + 1 rounds, we know the cheapest prices using at most k + 1 flights.

That exactly matches the problem.

The important detail is that each round must use a copy of the previous distance array.

Without a copy, updates from the current round could be reused immediately, accidentally allowing too many flights in one round.

Algorithm

Use dist, where:

dist[city]

means the cheapest cost to reach city using the number of flights allowed so far.

Initialize:

dist[src] = 0

All other cities start as infinity.

Then repeat k + 1 times:

1. Copy the current distances into next_dist.
2. For every flight (u, v, price):
   1. If dist[u] is reachable, try flying from u to v.
   2. Update next_dist[v].
3. Replace dist with next_dist.

After the loop, if dist[dst] is still infinity, return -1.

Otherwise, return dist[dst].

Correctness

We prove that after r relaxation rounds, dist[x] is the cheapest cost to reach city x using at most r flights.

Before any relaxation, dist[src] = 0 and all other cities are unreachable. This is correct for using at most 0 flights.

Assume the statement is true before round r + 1. During this round, every route using at most r + 1 flights either already used at most r flights, or it is formed by taking a route with at most r flights to some city u, then one more flight from u to v.

The algorithm checks every flight (u, v, price) and updates v using the previous round distance to u. Therefore, it considers exactly all routes that can be formed with one additional flight.

Because the algorithm uses a copied array, a route cannot use two new flights during the same round. Thus, round r + 1 represents at most r + 1 flights, not more.

By induction, after k + 1 rounds, dist[dst] is the cheapest cost to reach dst using at most k + 1 flights, which is the same as at most k stops.

Therefore, the algorithm returns the correct answer.

Complexity

Let m = len(flights).

Since k < n, the time can also be written as O(nm) in the worst case.

Implementation

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

        for _ in range(k + 1):
            next_dist = dist.copy()

            for start, end, price in flights:
                if dist[start] == inf:
                    continue

                next_dist[end] = min(
                    next_dist[end],
                    dist[start] + price
                )

            dist = next_dist

        if dist[dst] == inf:
            return -1

        return dist[dst]

Code Explanation

We start with all cities unreachable:

dist = [inf] * n

The source city costs 0 to reach:

dist[src] = 0

We perform k + 1 rounds because at most k stops means at most k + 1 flights:

for _ in range(k + 1):

At the start of each round, we copy the current distances:

next_dist = dist.copy()

This preserves the boundary between routes using at most the previous number of flights and routes using one more flight.

Then we scan all flights:

for start, end, price in flights:

If the start city is not reachable yet, this flight cannot help:

if dist[start] == inf:
    continue

Otherwise, try using this flight:

next_dist[end] = min(
    next_dist[end],
    dist[start] + price
)

After processing all flights, the next distances become current:

dist = next_dist

Finally, return -1 if the destination was never reached:

if dist[dst] == inf:
    return -1

Testing

def run_tests():
    s = Solution()

    assert s.findCheapestPrice(
        3,
        [[0, 1, 100], [1, 2, 100], [0, 2, 500]],
        0,
        2,
        1,
    ) == 200

    assert s.findCheapestPrice(
        3,
        [[0, 1, 100], [1, 2, 100], [0, 2, 500]],
        0,
        2,
        0,
    ) == 500

    assert s.findCheapestPrice(
        4,
        [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 3, 500]],
        0,
        3,
        1,
    ) == 500

    assert s.findCheapestPrice(
        4,
        [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 3, 500]],
        0,
        3,
        2,
    ) == 300

    assert s.findCheapestPrice(
        3,
        [[0, 1, 100]],
        0,
        2,
        1,
    ) == -1

    print("all tests passed")

run_tests()

Test coverage: