Cheapest Flights Within K Stops

Medium Graphs Dijkstra Original on LeetCode

Reported atGoogle Airbnb Flipkart Swiggy

Cheapest Flights Within K Stops is a medium graphs problem solved with the dijkstra pattern. The best approach, optimal (bellman-ford with k + 1 rounds), runs in O(k · E) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (dfs over routes) up.

Problem

There are n cities numbered 0 to n - 1. Each entry flights[i] = [from, to, price] is a one-way flight from city from to city to that costs price.

Return the cheapest total price to travel from src to dst using at most k stops (a stop is any city you land in between src and dst). If no such route exists, return -1.

Examples

Example 1

Input: n = 4, flights = [[0,1,50],[1,3,50],[0,2,20],[2,1,10],[0,3,200]], src = 0, dst = 3, k = 1
Output: 100
Why: With at most one stop, 0 -> 1 -> 3 costs 100. The cheaper 0 -> 2 -> 1 -> 3 (80) needs two stops.

Example 2

Input: n = 4, flights = [[0,1,50],[1,3,50],[0,2,20],[2,1,10],[0,3,200]], src = 0, dst = 3, k = 2
Output: 80
Why: Two stops are now allowed, so 0 -> 2 -> 1 -> 3 for 20 + 10 + 50 = 80 wins.

Example 3

Input: n = 3, flights = [[0,1,5],[1,2,5]], src = 0, dst = 2, k = 0
Output: -1
Why: The only route needs one stop at city 1, but no stops are allowed.

Constraints

1 <= n <= 100
0 <= flights.length <= n * (n - 1) / 2; each flight is [from, to, price] with from != to.
1 <= price <= 10^4; there is at most one flight per ordered pair of cities.
0 <= src, dst, k < n and src != dst.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force (DFS over routes)	`O(E^(k+1)) worst case`	`O(n + E)`
Optimal (Bellman-Ford with k + 1 rounds)	`O(k · E)`	`O(n)`

1Brute force (DFS over routes)

TimeO(E^(k+1)) worst caseWithout memory of earlier work, the search can branch along every flight at every level up to depth k + 1.

SpaceO(n + E)The adjacency list plus a recursion stack of depth at most k + 1.

Try every route from src that uses at most k + 1 flights and keep the cheapest one that ends at dst. Prune a branch once its cost already reaches the best answer found.

Build an adjacency list of outgoing flights.
DFS(city, flightsLeft, cost): if city == dst, update the best and stop.
If no flights are left or cost >= best, return.
Otherwise follow every outgoing flight with flightsLeft - 1.

class Solution {
    private int best = Integer.MAX_VALUE;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] f : flights) adj.get(f[0]).add(new int[] { f[1], f[2] });
        best = Integer.MAX_VALUE;
        dfs(adj, src, dst, k + 1, 0);
        return best == Integer.MAX_VALUE ? -1 : best;
    }

    private void dfs(List<List<int[]>> adj, int city, int dst, int left, int cost) {
        if (city == dst) { best = Math.min(best, cost); return; }
        if (left == 0 || cost >= best) return;
        for (int[] e : adj.get(city)) dfs(adj, e[0], dst, left - 1, cost + e[1]);
    }
}

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        adj = [[] for _ in range(n)]
        for a, b, p in flights:
            adj[a].append((b, p))
        self.best = float('inf')

        def dfs(city: int, left: int, cost: int) -> None:
            if city == dst:
                self.best = min(self.best, cost)
                return
            if left == 0 or cost >= self.best:
                return
            for nxt, p in adj[city]:
                dfs(nxt, left - 1, cost + p)

        dfs(src, k + 1, 0)
        return -1 if self.best == float('inf') else self.best

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<pair<int, int>>> adj(n);
        for (auto& f : flights) adj[f[0]].push_back({f[1], f[2]});
        best = INT_MAX;
        dfs(adj, src, dst, k + 1, 0);
        return best == INT_MAX ? -1 : best;
    }

private:
    int best = INT_MAX;

    void dfs(vector<vector<pair<int, int>>>& adj, int city, int dst, int left, int cost) {
        if (city == dst) { best = min(best, cost); return; }
        if (left == 0 || cost >= best) return;
        for (auto& e : adj[city]) dfs(adj, e.first, dst, left - 1, cost + e.second);
    }
};

function findCheapestPrice(n, flights, src, dst, k) {
    const adj = Array.from({ length: n }, () => []);
    for (const [a, b, p] of flights) adj[a].push([b, p]);
    let best = Infinity;
    function dfs(city, left, cost) {
        if (city === dst) { best = Math.min(best, cost); return; }
        if (left === 0 || cost >= best) return;
        for (const [nxt, p] of adj[city]) dfs(nxt, left - 1, cost + p);
    }
    dfs(src, k + 1, 0);
    return best === Infinity ? -1 : best;
}

2Optimal (Bellman-Ford with k + 1 rounds)

TimeO(k · E)k + 1 rounds, each scanning all E flights once.

SpaceO(n)Two distance arrays of size n.

After round r, dist[v] is the cheapest cost to reach v using at most r flights. Each round relaxes every flight, but reads from a copy of the previous round so a single round never chains two flights together.

dist[src] = 0, every other city = infinity.
Repeat k + 1 times: copy dist into next; for each flight (a, b, p) with dist[a] finite, set next[b] = min(next[b], dist[a] + p); then dist = next.
Return dist[dst], or -1 if it is still infinity.

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

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):
            nxt = dist[:]
            for a, b, p in flights:
                if dist[a] == INF:
                    continue
                if dist[a] + p < nxt[b]:
                    nxt[b] = dist[a] + p
            dist = nxt
        return -1 if dist[dst] == INF else dist[dst]

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        const int INF = INT_MAX;
        vector<int> dist(n, INF);
        dist[src] = 0;
        for (int round = 0; round <= k; round++) {
            vector<int> next = dist;
            for (auto& f : flights) {
                if (dist[f[0]] == INF) continue;
                int cand = dist[f[0]] + f[2];
                if (cand < next[f[1]]) next[f[1]] = cand;
            }
            dist = next;
        }
        return dist[dst] == INF ? -1 : dist[dst];
    }
};

function findCheapestPrice(n, flights, src, dst, k) {
    let dist = new Array(n).fill(Infinity);
    dist[src] = 0;
    for (let round = 0; round <= k; round++) {
        const next = dist.slice();
        for (const [a, b, p] of flights) {
            if (dist[a] === Infinity) continue;
            if (dist[a] + p < next[b]) next[b] = dist[a] + p;
        }
        dist = next;
    }
    return dist[dst] === Infinity ? -1 : dist[dst];
}

Edge cases to test

No route at all from src to dst (answer -1)
A direct flight that is more expensive than a route with stops
The cheapest route uses too many stops, so a pricier route with fewer stops is the answer
k = 0: only a direct flight counts

Hints

Hint 1

A route with at most k stops uses at most k + 1 flights. Think in terms of edges, not stops.

Hint 2

Plain Dijkstra keeps only the cheapest cost per city, but a more expensive arrival with fewer flights used can still matter.

Hint 3

Relax every flight k + 1 times, each round building only on the costs from the previous round (Bellman-Ford with a copy).

FAQ

What is the best time complexity for Cheapest Flights Within K Stops?

Optimal (Bellman-Ford with k + 1 rounds) runs in O(k · E) time and O(n) extra space. k + 1 rounds, each scanning all E flights once.

Which pattern does Cheapest Flights Within K Stops use?

It is a graphs problem that uses the dijkstra pattern. Other problems with the same pattern: Network Delay Time, Find the City With the Smallest Number of Neighbors at a Threshold Distance.

Is there a brute force solution for Cheapest Flights Within K Stops?

Yes. Brute force (DFS over routes) takes O(E^(k+1)) worst case time and O(n + E) space. Try every route from src that uses at most k + 1 flights and keep the cheapest one that ends at dst.

Which edge cases should I test for Cheapest Flights Within K Stops?

No route at all from src to dst (answer -1); A direct flight that is more expensive than a route with stops; The cheapest route uses too many stops, so a pricier route with fewer stops is the answer; k = 0: only a direct flight counts.