Cheapest Flights Within K Stops

Medium Problem 113 of 151 Java and Python

Problem

There are n cities and flights[i] = [from, to, price]. Given src, dst and k, return the cheapest price from src to dst with **at most k stops** (k + 1 flights), or -1 if there is no such route.

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
Why: 0 → 1 → 3. The cheaper 0 → 1 → 2 → 3 needs 2 stops.

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: same flights, k = 0
Output: 500
Why: Only a direct flight is allowed.

Constraints

1 ≤ n ≤ 100
0 ≤ k < n
1 ≤ price ≤ 10⁴

Explanation

Plain Dijkstra can settle a city through a cheap path that uses too many stops and then miss a slightly dearer path that fits. The stop limit has to be part of the search.

Bellman-Ford fits naturally: after round i, price[v] is the cheapest cost using at most i flights. Run exactly k + 1 rounds, and relax each round from a copy of the previous prices so one round never chains two flights.

Approach 1 · Better

BFS by number of flights

Time O(k · E)
Space O(n + E)

BFS level by level, where each level is one more flight. Only continue from a city when you reached it more cheaply than before.

Queue (src, 0) and set best[src] = 0.
Process up to k + 1 levels: for each (city, cost), try every outgoing flight; if cost + price < best[next], update and enqueue.
Return best[dst], or -1.

Java

import java.util.*;

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] f : flights) {
            graph.get(f[0]).add(new int[] { f[1], f[2] });
        }
        int[] best = new int[n];
        Arrays.fill(best, Integer.MAX_VALUE);
        best[src] = 0;
        Deque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[] { src, 0 });
        for (int flightsTaken = 0; flightsTaken <= k && !queue.isEmpty(); flightsTaken++) {
            for (int i = queue.size(); i > 0; i--) {
                int[] current = queue.poll();
                for (int[] edge : graph.get(current[0])) {
                    int cost = current[1] + edge[1];
                    if (cost < best[edge[0]]) {
                        best[edge[0]] = cost;
                        queue.add(new int[] { edge[0], cost });
                    }
                }
            }
        }
        return best[dst] == Integer.MAX_VALUE ? -1 : best[dst];
    }
}

Python

from collections import defaultdict, deque

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        graph = defaultdict(list)
        for u, v, p in flights:
            graph[u].append((v, p))
        best = [float("inf")] * n
        best[src] = 0
        queue = deque([(src, 0)])
        for _ in range(k + 1):
            for _ in range(len(queue)):
                city, cost = queue.popleft()
                for nxt, price in graph[city]:
                    if cost + price < best[nxt]:
                        best[nxt] = cost + price
                        queue.append((nxt, cost + price))
        return -1 if best[dst] == float("inf") else best[dst]

Approach 2 · Optimal

Bellman-Ford with k + 1 rounds

Time O(k · E)
Space O(n)

Each round allows one more flight. Relax every flight using the previous round's prices, kept in a copy.

price[src] = 0, others infinity.
Repeat k + 1 times: copy price to next; for each flight (u, v, p), if price[u] is finite, next[v] = min(next[v], price[u] + p); set price = next.
Return price[dst], or -1.

Java

import java.util.*;

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[] price = new int[n];
        Arrays.fill(price, Integer.MAX_VALUE);
        price[src] = 0;
        for (int round = 0; round <= k; round++) {
            int[] next = price.clone();
            for (int[] f : flights) {
                if (price[f[0]] != Integer.MAX_VALUE && price[f[0]] + f[2] < next[f[1]]) {
                    next[f[1]] = price[f[0]] + f[2];
                }
            }
            price = next;
        }
        return price[dst] == Integer.MAX_VALUE ? -1 : price[dst];
    }
}

Python

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        price = [float("inf")] * n
        price[src] = 0
        for _ in range(k + 1):
            nxt = price[:]
            for u, v, p in flights:
                if price[u] + p < nxt[v]:
                    nxt[v] = price[u] + p
            price = nxt
        return -1 if price[dst] == float("inf") else price[dst]

Complexity compared

Approach	Time	Space
Better BFS by number of flights	O(k · E)	O(n + E)
Optimal Bellman-Ford with k + 1 rounds	O(k · E)	O(n)

Key takeaways

Relaxing from a copy is what limits each round to one extra edge; relaxing in place could chain several flights in one round.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem