Cheapest Flights Within K Stops

Difficulty: Medium Source: NeetCode

Problem

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

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.

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

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

Constraints:

• 1 <= n <= 100
• 0 <= flights.length <= (n * (n-1) / 2)
• flights[i].length == 3
• 0 <= src, dst, k < n
• src != dst

Prerequisites

Before attempting this problem, you should be comfortable with:

• Bellman-Ford Algorithm — relaxing edges over multiple iterations
• BFS / Dijkstra — shortest path with state augmentation
• Dynamic Programming on Graphs — building up shortest paths iteration by iteration

1. Bellman-Ford (k+1 Iterations)

Intuition

Standard Dijkstra doesn’t work here because we have a constraint on the number of stops, not just the cost. Bellman-Ford is a great fit: each iteration relaxes all edges once, which corresponds to taking one more flight. After k+1 iterations (k stops means k+1 flights), dist[dst] gives us the cheapest cost.

The critical trick: use a copy of the previous iteration’s distances when updating, to prevent using more than one edge per iteration (otherwise you might chain multiple flights in a single round).

Algorithm

1. Initialize dist = [inf] * n, dist[src] = 0.
2. Repeat k+1 times:
   • Make a copy temp = dist[:].
   • For each flight (u, v, price): if dist[u] + price < temp[v], update temp[v].
   • Set dist = temp.
3. Return dist[dst] if not infinity, else -1.

Solution

def findCheapestPrice_bf(n, flights, src, dst, k):
    dist = [float('inf')] * n
    dist[src] = 0

    for _ in range(k + 1):  # k stops = k+1 flights
        temp = dist[:]
        for u, v, price in flights:
            if dist[u] != float('inf') and dist[u] + price < temp[v]:
                temp[v] = dist[u] + price
        dist = temp

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


flights1 = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
print(findCheapestPrice_bf(4, flights1, 0, 3, 1))  # 700

flights2 = [[0,1,100],[1,2,100],[0,2,500]]
print(findCheapestPrice_bf(3, flights2, 0, 2, 1))  # 200

print(findCheapestPrice_bf(3, flights2, 0, 2, 0))  # 500

Complexity

• Time: O(k * E) where E is number of flights
• Space: O(n) — distance arrays

2. BFS with State (Node, Stops Remaining)

Intuition

Model this as a BFS where state = (current_city, stops_remaining). We track the cheapest cost to reach each (city, stops) pair. Use a min-heap to always process the cheapest option first (Dijkstra-style). This avoids exploring paths that are guaranteed to be more expensive.

The key difference from standard Dijkstra is that we can visit the same city multiple times — once for each different number of stops remaining — because fewer stops used might allow cheaper paths later.

Algorithm

1. Build adjacency list from flights.
2. Push (0, src, k+1) — (cost, city, remaining_stops) — into min-heap.
3. Track visited = {city: best_remaining_stops} to prune.
4. While heap is not empty:
   • Pop (cost, city, stops).
   • If city == dst, return cost.
   • If stops == 0, skip (no more flights allowed).
   • For each neighbor (next, price):
     • If we can reach (next, stops-1) cheaper than before, push to heap.
5. Return -1 if destination not reached.

Solution

import heapq
from collections import defaultdict

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

    # (cost, city, stops_remaining)
    heap = [(0, src, k + 1)]
    # best cost to reach city with at least `stops` remaining
    visited = {}  # city -> best stops remaining at that cost

    while heap:
        cost, city, stops = heapq.heappop(heap)

        if city == dst:
            return cost

        if stops == 0:
            continue

        # Prune: if we've been here with >= stops remaining, skip
        if city in visited and visited[city] >= stops:
            continue
        visited[city] = stops

        for next_city, price in graph[city]:
            heapq.heappush(heap, (cost + price, next_city, stops - 1))

    return -1


flights1 = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
print(findCheapestPrice(4, flights1, 0, 3, 1))  # 700

flights2 = [[0,1,100],[1,2,100],[0,2,500]]
print(findCheapestPrice(3, flights2, 0, 2, 1))  # 200

print(findCheapestPrice(3, flights2, 0, 2, 0))  # 500

Complexity

• Time: O(k * E * log(k * n)) — heap operations with the stops dimension added
• Space: O(k * n) — state space

Common Pitfalls

Forgetting to copy distances in Bellman-Ford. If you update dist in-place during an iteration, you might chain multiple flights in one round. Always work from a snapshot (temp = dist[:]) and write into temp.

K stops vs K+1 flights confusion. k stops means k+1 edges (flights). Loop k+1 times in Bellman-Ford, or allow k+1 transitions in BFS.

Pruning too aggressively in Dijkstra approach. Unlike standard Dijkstra, you can revisit a city with fewer stops remaining — that might unlock cheaper paths later. The visited check should account for the number of stops, not just the city.