Cheapest Flights Within K Stops

HardGraphsbellman-ford

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given n cities numbered from 0 to n - 1, connected by one-way flights. The flights are described by a list flights, where each entry flights[i] = [from, to, price] means there is a directed flight from city from to city to costing price. You are also given three integers: a starting city src, a destination city dst, and an integer k. Return the **cheapest total price** to travel from src to dst using **at most k stops** (intermediate cities). If no such route exists, return -1. A "stop" is an intermediate city between src and dst. For example, a direct flight from src to dst uses 0 stops, while a route src -> a -> dst uses 1 stop. This means a valid route may use at most k + 1 flights in total.

Examples

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
The cheapest route using at most 1 stop is 0 -> 1 -> 3, costing 100 + 600 = 700. The route 0 -> 1 -> 2 -> 3 is cheaper (400) but it uses 2 stops, which exceeds the limit.
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
With up to 1 stop, the route 0 -> 1 -> 2 costs 200, which beats the direct flight 0 -> 2 costing 500.
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
With 0 stops allowed, only the direct flight 0 -> 2 (price 500) is valid; the two-hop route is not permitted.

Constraints

  • 1 <= n <= 100
  • 0 <= flights.length <= n * (n - 1)
  • flights[i].length == 3
  • 0 <= from, to < n
  • from != to
  • 1 <= price <= 10^4
  • There will not be any duplicate directed flights (same from and to pair).
  • 0 <= src, dst < n
  • src != dst
  • 0 <= k < n

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.