Cheapest Flights Within K Stops

MEDIUM✓ CHIP-TIMEDLC #787 — FULL STATEMENT ↗

The drill: Flights connect cities with a price each. Find the cheapest way from a source city to a destination that uses at most k layovers — cheapest isn't always the route with the fewest hops.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A set of one-way flights arrives, each with its own price, along with a source city, a destination city, and a maximum number of layovers allowed along the way.

A route qualifies only if it uses at most that many layovers — one layover fewer than the number of flights taken. Among every qualifying route, the task is to find the cheapest total price.

If no route from the source to the destination fits inside the layover budget, that has to be signaled distinctly rather than treated as a price of zero.

EX 01

n = 3 · flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]] · src = 0 · dst = 2 · k = 1

→ 200

ONE STOP UNLOCKS THE CHEAPER RELAY

EX 02

n = 3 · flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]] · src = 0 · dst = 2 · k = 0

→ 500

ZERO STOPS FORCES THE DIRECT, PRICIER FLIGHT

EX 03

n = 3 · flights = [[0, 1, 10]] · src = 0 · dst = 2 · k = 5

→ -1

DESTINATION IS SIMPLY UNREACHABLE

city and flight counts stay modest, each up to a few hundred
flight prices are positive integers
stop budget k limits layovers, not the count of flights
no qualifying route reports a distinct sentinel, not zero

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Plain shortest-path finds the globally cheapest route, full stop — but the cheapest route overall might need more layovers than the budget allows. The stop count is a hard constraint on the search, not a tiebreaker.

HINT 2 THE STRUCTURE

Think in rounds instead of a running frontier: after round i, you know the cheapest way to reach every city using at most i flights. Round i+1 only ever extends those, one more flight each.

HINT 3 ONE STEP FROM THE ANSWER

Bellman-Ford, capped at k+1 rounds: each round, relax every flight edge against LAST round's prices — never this round's half-updated ones, or a city could sneak in an extra hop for free.

COACH'S BOARD — THE PATTERN, STEP BY STEP

PRICES, FROZEN BY THE ROUNDPATTERN · BELLMAN-FORD, K+1 ROUNDSflights: 0→1(100) 1→2(100) 0→2(500) · src=0 dst=2 k=1

STEP 1

Row 0: node 0 starts at cost 0, every other node unreached. Each round below allows exactly one more flight.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/cheapest-flights-within-k-stops.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        dist = [float('inf')] * n
        dist[src] = 0
        for _ in range(k + 1):
            new_dist = dist[:]
            for u, v, w in flights:
                if dist[u] != float('inf') and dist[u] + w < new_dist[v]:
                    new_dist[v] = dist[u] + w
            dist = new_dist
        return dist[dst] if dist[dst] != float('inf') else -1

TIME O(K·E)SPACE O(V)PYTHON · RACE PACE · 11 LN

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for u, v, w in flights:
            graph[u].append((v, w))
        best = [float('inf')]

        def dfs(u, cost, stops):
            if cost >= best[0]:
                return
            if u == dst:
                best[0] = cost
                return
            if stops > k:
                return
            for v, w in graph[u]:
                dfs(v, cost + w, stops + 1)

        dfs(src, 0, 0)
        return best[0] if best[0] != float('inf') else -1

TIME O(E^K)SPACE O(K)PYTHON · TRAINING PACE · 20 LN

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

TIME O(K·E)SPACE O(V)JAVA · RACE PACE · 18 LN

class Solution {
    private int best;
    private int k;
    private Map<Integer, List<int[]>> graph;
    private int dst;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        this.k = k;
        this.dst = dst;
        this.best = Integer.MAX_VALUE;
        graph = new HashMap<>();
        for (int[] f : flights) {
            graph.computeIfAbsent(f[0], x -> new ArrayList<>()).add(new int[] { f[1], f[2] });
        }
        dfs(src, 0, 0);
        return best == Integer.MAX_VALUE ? -1 : best;
    }

    private void dfs(int u, int cost, int stops) {
        if (cost >= best) return;
        if (u == dst) {
            best = cost;
            return;
        }
        if (stops > k) return;
        for (int[] edge : graph.getOrDefault(u, Collections.emptyList())) {
            dfs(edge[0], cost + edge[1], stops + 1);
        }
    }
}

TIME O(E^K)SPACE O(K)JAVA · TRAINING PACE · 30 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED