Cheapest Flights Within K Stops | Leetcode 787 | Easy BFS Approach in Python

Solve “Cheapest Flights Within K Stops” (LeetCode 787) in plain Python using a BFS queue and a cost array. Learn the intuition, code, and dry-run for cheapest flights first-time success.

Here’s the [Problem Link] to begin with.

1. What does the problem ask?

You have n cities numbered 0 … n-1 and a list of flights
[from, to, price].
You must fly from src to dst but may take at most k intermediate stops
(so at most k + 1 flights in total).

Return the cheapest possible price.
If no such route exists, return -1.

2. Quick examples

3. Intuition & approach

3.1 Graph view

Cities are nodes; flights are directed edges with weights = prices.

3.2 Why not plain Dijkstra?

Dijkstra does not limit the number of edges; it might return a cheaper path that uses too many stops.
We need a structure that also keeps track of how many flights we have taken so far.

3.3 BFS with cost pruning

1. Level = stops so far
   A standard BFS queue processes nodes layer by layer; here each layer means “one more flight taken”.
2. State tuple (stopsUsed, city, costSoFar)
   We never push a state whose stopsUsed already exceeded k + 1 flights.
3. min_cost[city] array
   Stores the cheapest price found so far for that city with any number of stops ≤ k + 1.
   We only push a new state if we have really improved that city’s cost.
4. Stop early
   We may still keep exploring even after seeing dst once, because another path with the same or fewer stops could be cheaper—but the min_cost check prevents endless work.

This idea is similar to Bellman-Ford limited to k + 1 rounds, but implemented with a queue for clarity.

4 Code

import sys
from collections import deque
from typing import List


class Solution:
    def findCheapestPrice(
        self, n: int, flights: List[List[int]], src: int, dst: int, k: int
    ) -> int:
        # build adjacency list: u -> [(v, price), ...]
        adj_list = [[] for _ in range(n)]
        for u, v, cost in flights:
            adj_list[u].append([v, cost])

        # cost array – start city = 0, others = +∞
        min_cost = [sys.maxsize for _ in range(n)]
        min_cost[src] = 0

        # BFS queue holds (stopsUsed, city, costSoFar)
        queue = deque()
        queue.append([0, src, 0])

        while queue:
            stops, city, cost = queue.popleft()

            # Explore outward flights
            for nxt, price in adj_list[city]:
                new_cost  = cost + price
                new_stops = stops + 1       # we have used one more flight

                # Respect stop limit: total flights ≤ k + 1
                if new_stops == k + 1 and nxt != dst:
                    continue

                # Relaxation: only continue if cheaper
                if new_cost < min_cost[nxt]:
                    min_cost[nxt] = new_cost
                    queue.append([new_stops, nxt, new_cost])

        return -1 if min_cost[dst] == sys.maxsize else min_cost[dst]

5. Step-by-step explanation

1. Adjacency list gives O(1) access to outgoing flights.
2. min_cost prevents revisiting a city with a worse or equal total price.
3. stops counter ensures we never exceed k + 1 flights.
4. When queue empties, every path with ≤ k stops has been tried; min_cost[dst] is the answer.

6. Dry run (tiny graph)

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

Cheapest price found = 200.

7. Complexity

V = n, E = len(flights).

8. Conclusion

• Cheapest Flights Within K Stops is best tackled by a BFS-style traversal that tracks both price and stops.
• A simple queue plus a min_cost array avoids the heavier Bellman-Ford double loop.
• Remember the key SEO phrase, cheapest flights—and this quick Dijkstra-inspired idea to keep your interview path cost-effective!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.