Skip to main content

787. Cheapest Flights Within K Stops

medium

Find the cheapest price from src to dst using at most k stops on a weighted directed graph. Standard Dijkstra doesn't apply cleanly because of the hop constraint — Bellman-Ford limited to k+1 relaxations is the canonical solution.

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] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei. 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 <= fromi, toi < n
  • fromi != toi
  • 1 <= pricei <= 10^4
  • There will not be any multiple flights between two cities.
  • 0 <= src, dst, k < n
  • src != dst

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

Example 2

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

Explanation: The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Example 3

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

Explanation: The optimal path with no stops from city 0 to 2 is marked in blue and has cost 500.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Dijkstra alone is unsafe: you might reject a cheap-but-many-hops path that ultimately wins under the hop budget.

Hint 2

Bellman-Ford for exactly k+1 iterations works: each iteration extends the path by one edge.

Hint 3

Critical detail: read prices from a snapshot of the previous iteration, not the live array, or one iteration would chain multiple edges.

Solution approach

Reveal approach

Bellman-Ford limited to k+1 edge relaxations. Initialize cost[] of size n with infinity, cost[src] = 0. Repeat k+1 times: take a SNAPSHOT of cost, then for each flight (u, v, price), if snapshot[u] + price < cost[v], update cost[v]. Using the snapshot is what keeps each iteration to exactly one new edge; without it, multiple edges could chain within a single iteration and you'd over-relax. After k+1 iterations, return cost[dst] if it's finite, else -1. There's also a Dijkstra-with-state-(node, stops) variant that pushes (cost, node, stops) into a min-heap and continues only while stops <= k; both run in similar time. Bellman-Ford gives O((k+1) * E), heap-Dijkstra is O(E * k * log(E*k)).

Complexity

Time
O((k + 1) * E)
Space
O(n)

Related patterns

  • bellman-ford
  • dijkstra
  • shortest-path
  • graph

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Uber
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Cheapest Flights Within K Stops and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →