Katkat
Back

How to find the cheapest flight within K stops

StripeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to find the shortest path in a weighted graph under a specific constraint on the number of edges (stops).

Problem Statement

You are given a list of flights, where each flights[i] = [from, to, price]. You are also given three integers: n (number of cities), src (starting city), dst (destination city), and k (the maximum number of stops allowed).

Your task is to 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
  • 0 <= from, to, src, dst < n
  • 0 <= price <= 10,000
  • 0 1 -> 3 costs 100 + 600 = 700. The route 0 -> 1 -> 2 -> 3 costs 100 + 100 + 200 = 400, but that uses 2 stops, exceeding the limit k=1`.

Function Signature

def findCheapestPrice(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:

Hints

Hint 1

Consider this as a shortest path problem in a graph where edge weights are flight prices.

Hint 2

Standard Dijkstra's algorithm might fail here because the constraint is on the number of edges, not just the total cost.

Hint 3

Think about using dynamic programming or a modified Bellman-Ford approach where the state tracks the number of stops taken.

Follow-up questions

  • How would your approach change if you needed to track the actual path taken in addition to the cost?
  • What is the time and space complexity of your solution, and how does it scale with a very large number of cities?
  • How would you modify the algorithm if there were a time-of-day constraint for each flight?