Cheapest Flights Within K Stops

Cheapest Flights Within K Stops

What is this problem about?

The "Cheapest Flights Within K Stops interview question" is a shortest-path problem with an additional constraint. You are given a set of cities connected by flights with specific costs. Your goal is to find the minimum price to fly from a src city to a dst city, but you are limited to a maximum of k stops (meaning at most $k+1$ total flights).

Why is this asked in interviews?

This "Cheapest Flights Within K Stops coding problem" is a favorite of companies like Apple, Uber, and Airbnb. It tests whether a candidate can adapt standard shortest-path algorithms (like Dijkstra's) to include a "budget" of stops. It evaluates the ability to handle multi-dimensional state (cost and stops) and prevents simple greedy solutions from working correctly.

Algorithmic pattern used

This problem can be solved using Breadth-First Search (BFS), Dijkstra's Algorithm, or Bellman-Ford.

1. BFS: Since we care about the number of stops, a level-by-level BFS is natural. Each level increment represents one more stop. Maintain an array min_costs to prune paths that are more expensive than what we've already found at a given city.
2. Modified Dijkstra: Use a priority queue to always explore the cheapest flight first. However, unlike standard Dijkstra, you might visit a city multiple times if a new path has fewer stops, even if it's slightly more expensive.
3. Bellman-Ford: Run the edge relaxation process exactly $k+1$ times.

Example explanation

Flights: (A->B, 100), (B->C, 100), (A->C, 500), $K = 1$.

• Path 1: A -> B -> C. Cost: 200. Stops: 1. (Valid).
• Path 2: A -> C. Cost: 500. Stops: 0. (Valid). Result: 200. If $K=0$, only Path 2 is valid. Result: 500.

Common mistakes candidates make

• Standard Dijkstra: Using standard Dijkstra without considering stops. A cheaper path with too many stops might prevent the algorithm from ever finding a valid path with slightly more cost.
• TLE with BFS: Not using a min_costs array to prune search branches, leading to exponential growth in explored paths.
• Off-by-one: Confusing "K stops" with "K flights." Remember that $K$ stops means $K+1$ flights.

Interview preparation tip

Master "Shortest Path" algorithms. This problem is the perfect example of why you must understand the why behind algorithms like Dijkstra. Practice identifying when a problem requires tracking an extra state variable beyond just the weight/cost.