22. Cheapest Flights Within K Stops

mediumAsked at Lyft

Minimize cost with a hop constraint — Lyft applies the same bounded shortest-path logic when optimizing multi-leg ride chains where passengers switch vehicles at hubs, keeping transfers under a service limit.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from, to, price]. You are also given three integers src, dst, and k. Return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Constraints

1 <= n <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= from, to < n
from != to
1 <= price <= 10^4
0 <= k < n
There will not be any multiple flights between two cities

Examples

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

Explanation: Cheapest route with at most 1 stop: 0 -> 1 -> 3 costs 700. Going via 2 stops (0->1->2->3) costs 400 but exceeds the k=1 limit.

Example 2

Input

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

Output

Approaches

1. Bellman-Ford bounded relaxation

Run Bellman-Ford for exactly k+1 rounds. Each round represents one leg of the journey. Keep a copy of the previous round's distances to avoid using the same edge twice in one round.

Time: O(k * E)
Space: O(V)

function findCheapestPrice(n, flights, src, dst, k) {
  let prices = new Array(n).fill(Infinity);
  prices[src] = 0;

  for (let i = 0; i <= k; i++) {
    const temp = [...prices];
    for (const [from, to, price] of flights) {
      if (prices[from] !== Infinity && prices[from] + price < temp[to]) {
        temp[to] = prices[from] + price;
      }
    }
    prices = temp;
  }

  return prices[dst] === Infinity ? -1 : prices[dst];
}

Tradeoff:

2. Dijkstra with stop tracking

Modified Dijkstra where heap state is [cost, node, stops]. Only enqueue neighbors if stops < k. Track minimum cost per (node, stops) to prune redundant paths.

Time: O(E * k * log(E * k))
Space: O(V * k)

function findCheapestPrice(n, flights, src, dst, k) {
  const graph = Array.from({ length: n }, () => []);
  for (const [from, to, price] of flights) graph[from].push([to, price]);

  // [cost, node, stops]
  const heap = [[0, src, 0]];
  const best = Array.from({ length: n }, () => new Array(k + 2).fill(Infinity));
  best[src][0] = 0;

  while (heap.length) {
    heap.sort((a, b) => a[0] - b[0]);
    const [cost, node, stops] = heap.shift();
    if (node === dst) return cost;
    if (stops > k) continue;
    for (const [next, price] of graph[node]) {
      const newCost = cost + price;
      if (newCost < best[next][stops + 1]) {
        best[next][stops + 1] = newCost;
        heap.push([newCost, next, stops + 1]);
      }
    }
  }
  return -1;
}

Tradeoff:

Lyft-specific tips

Lyft grades this problem on your ability to handle the stop constraint correctly — a classic trap is using standard Dijkstra and accidentally updating a node's cost after it's been 'settled.' Walk the interviewer through why you copy the price array in Bellman-Ford before relaxing. If you go Dijkstra, explain why you track stops in the heap state rather than globally per node.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Cheapest Flights Within K Stops and other Lyft interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →