Cheapest Flights Within K Stops

NeetCode: Cheapest Flights Within K Stops · LeetCode: 787. Cheapest Flights Within K Stops · Difficulty: Medium

There are n cities and flights given as [from, to, price]. Return the cheapest price from src to dst with at most k stops (so at most k + 1 flights), or -1 if there is no such route.

Example

Text

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     (0 -> 1 -> 3)

Input:  n = 3, flights = [[0,1,100], [1,2,100], [0,2,500]], src = 0, dst = 2, k = 1
Output: 200     (0 -> 1 -> 2)

Same flights, k = 0    Output: 500     (only the direct flight fits)

Plain Dijkstra does not apply directly: the cheapest path may use too many stops, and a pricier path with fewer stops must still be considered. The constraint is on the number of edges, which is what Bellman-Ford's rounds count.

Brute force: DFS over every route

Explore flights recursively, tracking the remaining number of flights allowed. Stop when the destination is reached (going further only adds cost, since prices are positive), stop when no flights remain, and prune any branch already costing at least the best answer found.

The graph is a list of adjacency lists, one int[]{to, price} per flight. Costs are held in a long so the sum cannot overflow int. The best price lives in a one-element long[] so the recursive calls can update it.

Java

import java.util.ArrayList;
import java.util.List;

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]});
        long[] best = {Long.MAX_VALUE};
        dfs(graph, src, dst, k + 1, 0, best);
        return best[0] == Long.MAX_VALUE ? -1 : (int) best[0];
    }

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

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] f1 = {{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}};
        System.out.println(s.findCheapestPrice(4, f1, 0, 3, 1));
        int[][] f2 = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
        System.out.println(s.findCheapestPrice(3, f2, 0, 2, 1));
        System.out.println(s.findCheapestPrice(3, f2, 0, 2, 0));
        System.out.println(s.findCheapestPrice(3, f2, 2, 0, 5));
    }
}

Output

With branching factor d (flights per city) there are up to d^(k+1) routes, and cycles can be revisited because the flight limit is what stops the recursion. Time: O(d^(k+1)) worst case. Space: O(k) recursion depth plus the graph.

Optimal: Bellman-Ford limited to k + 1 rounds

After round i of Bellman-Ford, dist[v] is the cheapest price to v using at most i flights, so exactly k + 1 rounds are run. Each round must relax edges using only the distances from the previous round; otherwise one round could chain several flights and break the stop limit. The code reads from dist and writes to a fresh copy next.

INF is Integer.MAX_VALUE, and the code checks dist[from] != INF before adding a price, so the sum never overflows int. Real totals are int sums, so very large prices would need long.

Java

import java.util.Arrays;

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) {
                int from = f[0], to = f[1], price = f[2];
                if (dist[from] != INF && dist[from] + price < next[to]) {
                    next[to] = dist[from] + price;
                }
            }
            dist = next;
        }
        return dist[dst] == INF ? -1 : dist[dst];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] f1 = {{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}};
        System.out.println(s.findCheapestPrice(4, f1, 0, 3, 1));
        int[][] f2 = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
        System.out.println(s.findCheapestPrice(3, f2, 0, 2, 1));
        System.out.println(s.findCheapestPrice(3, f2, 0, 2, 0));
        System.out.println(s.findCheapestPrice(3, f2, 2, 0, 5));
    }
}

Output

Walkthrough of the second example with k = 1 (2 rounds): after round 1, dist = [0, 100, 500]; after round 2, dist[2] = min(500, 100 + 100) = 200.

Time: O(k * E) (each of the k + 1 rounds also copies dist, adding O(k * n)). Space: O(n).