How do you solve Cheapest Flights Within K Stops?

Initialize a prices array with infinity for all cities except the source city set to 0. For k+1 iterations, create a temporary copy of prices. For each flight, if the source city's price is not infinity, update the destination city's price in the temporary array if a cheaper cost is found via this flight. After processing all flights, update the prices array with the temporary array. After k+1 iterations, if the destination city's price is still infinity, return -1; otherwise, return the price. This approach guarantees the cheapest price with at most k stops in O(k * E) time, where E is the number of flights.

Cheapest Flights Within K Stops

Q: What is the time complexity of Cheapest Flights Within K Stops?

O(k * E). The algorithm performs k+1 iterations, and in each iteration, it processes all E flights to relax edges. Each relaxation is O(1), so total time is O(k * E).

Q: What pattern does Cheapest Flights Within K Stops use?

The Pattern: Dynamic Programming (Bellman-Ford Relaxation with Edge Constraints) The Heuristic: When finding shortest paths with a constraint on the number of edges or stops, iteratively relax edges up to the allowed number of edges, using a temporary array to prevent intra-iteration interference and ensure correctness.

Medium Dynamic Programming

Problem

Given n cities numbered from 0 to n-1, a list of flights where each flight is represented as (source, destination, price), a starting city src, a destination city dst, and an integer k, return the cheapest price from src to dst with at most k stops. If no such route exists, return -1.

1 ≤ n ≤ 100
0 ≤ flights.length ≤ n * (n - 1) / 2
flights[i].length == 3
0 ≤ src, dst < n
0 ≤ k < n
1 ≤ price ≤ 10⁴

Example

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

Output: 200

The algorithm initializes the prices array with infinity except for the source city which is set to 0. It then iteratively relaxes the prices for up to k+1 edges (stops + 1). On the first iteration, it updates the price to city 1 as 100. On the second iteration, it updates the price to city 2 via city 1 as 200, which is cheaper than the direct flight costing 500. Since the maximum allowed stops is 1, this route is valid and the algorithm returns 200.

Approach

Straightforward Solution

A brute-force approach would enumerate all paths from src to dst with up to k stops, calculating their costs and returning the minimum. This approach is exponential in time and infeasible for large inputs.

Core Observation

The problem asks for the minimum cost path from src to dst with at most k stops, which translates to finding the shortest path with a constraint on the number of edges used. This is a classic shortest path problem with an additional constraint on path length.

Path to Optimal

Preview

Recognizing the problem as a shortest path with edge constraints suggests using a Dynamic Programming approach similar to the Bellman-Ford algorithm. Bellman-Ford relaxes edges repeatedly to find shortest paths with up to a certain number of edges…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize a prices array with infinity for all cities except the source city set to 0. For k+1 iterations, create a temporary copy of prices…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(k * E)

The algorithm performs k+1 iterations, and in each iteration, it processes all E flights to relax edges. Each relaxation is O(1), so total time is O(k * E).

Space

O(n)

The algorithm uses two arrays of size n to store prices and temporary prices. This auxiliary space scales linearly with the number of cities and is necessary to track the minimum costs.

Pattern Spotlight

Dynamic Programming (Bellman-Ford Relaxation with Edge Constraints)

When finding shortest paths with a constraint on the number of edges or stops, iteratively relax edges up to the allowed number of edges, using a temporary array to prevent intra-iteration interference and ensure correctness.

Solution

Python

1class Solution:
  def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
      prices = [float("inf")] * n
      prices[src] = 0
5
      for i in range(k + 1):
          tmp_prices = prices.copy()
          
          for s, d, p in flights:
              if prices[s] == float("inf"):
                  continue
              if prices[s] + p < tmp_prices[d]:
                  tmp_prices[d] = prices[s] + p
          prices = tmp_prices
      
      return prices[dst] if prices[dst] != float("inf") else -1

Step-by-Step Solution

Initialize Prices Array with Infinite Costs Except Source

3prices = [float("inf")] * n
4prices[src] = 0

Objective

To set up the initial cost estimates for reaching each city, starting with zero cost for the source and infinity for others.

Key Insight

Initializing the prices array with infinity represents that all cities are initially unreachable except the source city, which has zero cost. This setup forms the base case for the iterative relaxation process, allowing the algorithm to progressively find cheaper paths.

Interview Quick-Check

Core Logic

Setting prices[src] = 0 establishes the starting point for cost calculations, ensuring the source city is reachable at zero cost.

Common Pitfalls & Bugs

Failing to initialize non-source cities with infinity would cause incorrect cost comparisons and potentially invalid results.

Iteratively Relax Edges Up to k+1 Times to Update Minimum Prices

To progressively update the minimum cost to reach each city by considering all flights up to the allowed number of stops.

Return the Cheapest Price or -1 if Unreachable

To provide the final answer based on the computed minimum cost to reach the destination city.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 7 Critical

tmp_prices = prices.copy()

Create a temporary copy of the current prices array.

Copying prices prevents updates in the current iteration from affecting other relaxations, preserving the correctness of the Bellman-Ford relaxation process under edge constraints.

Line 4 Critical

prices[src] = 0

Set the source city's price to zero.

This anchors the starting point of the algorithm, indicating that the cost to reach the source city from itself is zero, enabling subsequent relaxations.

Line 12 Critical

if prices[s] + p < tmp_prices[d]:

Check if taking this flight offers a cheaper price to the destination city.

This conditional identifies opportunities to improve the minimum cost to reach the destination city by relaxing the edge.

Full line-by-line criticality + rationale for all 11 lines available on Pro.

Test Your Understanding

Why does the algorithm use a temporary copy of the prices array in each iteration instead of updating the prices array directly?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Cheapest Flights Within K Stops from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Cheapest Flights Within K Stops drill

or drill a free problem

1	`class Solution:`
2	`def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:`
3	`prices = [float("inf")] * n`
4	`prices[src] = 0`
5
6	`for i in range(k + 1):`
7	`tmp_prices = prices.copy()`
8
9	`for s, d, p in flights:`
10	`if prices[s] == float("inf"):`
11	`continue`
12	`if prices[s] + p < tmp_prices[d]:`
13	`tmp_prices[d] = prices[s] + p`
14	`prices = tmp_prices`
15
16	`return prices[dst] if prices[dst] != float("inf") else -1`