Cheapest Flights Within K Stops

The problem, simply

There are n cities. Each flight [from, to, price] goes one way and costs some money. You start in city src and want to reach city dst.

You may stop in at most k cities on the way. So you may take at most k + 1 flights. Give back the cheapest total price, or -1 if no trip fits the rule.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every trip. Start at src, take any flight, then any flight from there, and keep going while you still have flights left. Each time you land on dst, remember the price if it is the cheapest so far.

1. Build a list of flights leaving each city.
2. Walk deeper and deeper with a count of flights left, carrying the price so far.
3. Stop a path when it reaches dst, runs out of flights, or already costs more than the best answer.
4. Do not visit a city twice on one path. With positive prices a loop can never help.

class CheapestFlightsDfs {
    static int best;

    public static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        List<List<int[]>> out = new ArrayList<>();
        for (int i = 0; i < n; i++) out.add(new ArrayList<>());
        for (int[] f : flights) out.get(f[0]).add(new int[]{f[1], f[2]});

        best = Integer.MAX_VALUE;
        boolean[] onPath = new boolean[n];
        onPath[src] = true;
        dfs(out, src, dst, k + 1, 0, onPath);           // k stops means k + 1 flights
        return best == Integer.MAX_VALUE ? -1 : best;
    }

    static void dfs(List<List<int[]>> out, int city, int dst, int flightsLeft, int cost, boolean[] onPath) {
        if (cost >= best) return;                        // already too pricey
        if (city == dst) { best = cost; return; }
        if (flightsLeft == 0) return;
        for (int[] f : out.get(city)) {
            int next = f[0], price = f[1];
            if (onPath[next]) continue;
            onPath[next] = true;
            dfs(out, next, dst, flightsLeft - 1, cost + price, onPath);
            onPath[next] = false;                        // step back and try another flight
        }
    }
}

How long it takes: each step can branch to up to n cities and a path has up to k + 1 steps, so up to O(n^(k+1)) paths. Extra room: the flight lists O(n + E) and a path of depth k + 1.

Way 2: the clever way

Play the hopping game in rounds. After round r, price[c] is the cheapest way to reach city c using at most r flights. Each round looks at every flight once.

1. Set price[src] = 0 and every other price to infinity.
2. Repeat k + 1 times:
3. Copy the prices into next. For each flight u to v with cost w, if price[u] is known and price[u] + w < next[v], set next[v] = price[u] + w.
4. Replace price with next. At the end, price[dst] is the answer, or -1 if it is still infinity.

The copy is the whole trick. We read from last round's prices and write to this round's prices, so one round can only add one flight.

class CheapestFlightsRounds {
    public static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        final int INF = Integer.MAX_VALUE;
        int[] price = new int[n];
        Arrays.fill(price, INF);
        price[src] = 0;

        for (int round = 0; round <= k; round++) {       // k + 1 rounds, one flight each
            int[] next = Arrays.copyOf(price, n);        // write here, read from price
            for (int[] f : flights) {
                int u = f[0], v = f[1], w = f[2];
                if (price[u] != INF && price[u] + w < next[v]) {
                    next[v] = price[u] + w;
                }
            }
            price = next;
        }
        return price[dst] == INF ? -1 : price[dst];
    }

    public static void main(String[] args) {
        int[][] flights = {{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}};
        System.out.println(findCheapestPrice(4, flights, 0, 3, 1));  // 700
        System.out.println(findCheapestPrice(4, flights, 0, 3, 2));  // 400
    }
}

How long it takes: k + 1 rounds, each looks at all E flights, O(k * E). Extra room: two price arrays of size n, O(n).

Watch out for

• k counts stops, not flights. Run k + 1 rounds.
• Skip flights that start from a city with price infinity, or INF + w wraps around to a negative number.
• Plain Dijkstra on price alone is wrong: a cheap path with too many stops can settle a city before the pricier path with few stops arrives.
• If src == dst, the answer is 0 with no flights at all.

What interviewers ask next

• Can Dijkstra work here? Yes, if the heap holds {price, city, flightsUsed} and you allow a city to be visited again when it is reached with fewer flights. Keep bestFlights[city] and skip a pop only if it used more flights than a previous pop of that city.
• Can you do it as BFS? Yes. Go level by level with a queue, one level per flight, and stop after k + 1 levels. Keep the best price per city and only push improvements.
• How do you return the route too? Keep a parent per city per round, or store the path inside the queue entries.
• What if there were no stop limit? Then it is a plain shortest path with positive prices: use Dijkstra.

Remember this

Grown-up words: cities are vertices, flights are directed weighted edges, a round is one Bellman-Ford relaxation pass, the copy keeps the rounds layered so round r uses at most r edges, and the hopping game is dynamic programming over the number of edges used.