Skip to main content

26. Cheapest Flights Within K Stops

mediumAsked at Expedia

Find the cheapest flight from src to dst with at most k stops — this is one of Expedia's most direct algorithm-to-product problems, modeling their core flight search with a layover constraint.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i, to_i, price_i]. 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_i, to_i < n
  • from_i != to_i
  • 1 <= price_i <= 10^4
  • 0 <= k < n

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
700

Explanation: 0 → 1 ($100) → 3 ($600) = $700 with 1 stop.

Example 2

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

Approaches

1. Bellman-Ford with stop limit

Run k+1 rounds of Bellman-Ford relaxation, copying the previous round's distances before each round to enforce the stop constraint.

Time
O(k * flights.length)
Space
O(n)
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. BFS level-by-level (stops as levels)

BFS where each level represents one additional stop. Maintain a cost map; prune branches that exceed known best costs. Naturally enforces the k-stop limit.

Time
O(k * flights.length)
Space
O(n)
function findCheapestPrice(n, flights, src, dst, k) {
  const graph = new Map();
  for (const [from, to, price] of flights) {
    if (!graph.has(from)) graph.set(from, []);
    graph.get(from).push([to, price]);
  }

  const costs = new Array(n).fill(Infinity);
  costs[src] = 0;

  let queue = [[src, 0]];

  for (let stop = 0; stop <= k && queue.length; stop++) {
    const next = [];
    for (const [node, cost] of queue) {
      for (const [neighbor, price] of (graph.get(node) || [])) {
        const newCost = cost + price;
        if (newCost < costs[neighbor]) {
          costs[neighbor] = newCost;
          next.push([neighbor, newCost]);
        }
      }
    }
    queue = next;
  }

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

Tradeoff:

Expedia-specific tips

This is a signature Expedia problem — they built a travel-search company on exactly this abstraction. Name both approaches and explain the copy-temp trick in Bellman-Ford: without it, you let a single round make multiple hops and break the stop constraint. Expect a follow-up on negative prices (Bellman-Ford handles them; Dijkstra does not).

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 Expedia interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →