# Cheapest Flights Within K Stops
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/cheapest-flights-within-k-stops)
Canonical: https://scaleengineer.com/dsa/problems/cheapest-flights-within-k-stops
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Heap (Priority Queue), Graph
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Snowflake](https://scaleengineer.com/companies/snowflake), [Coupang](https://scaleengineer.com/companies/coupang), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Snap](https://scaleengineer.com/companies/snap), [Cloudera](https://scaleengineer.com/companies/cloudera), [Stripe](https://scaleengineer.com/companies/stripe)
---
## 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`.

**Example 1:**

![](https://assets.glich.co/dsa/cheapest-flights-within-k-stops/image0.png) 

**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
**Explanation:**
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

**Example 2:**

![](https://assets.glich.co/dsa/cheapest-flights-within-k-stops/image1.png) 

**Input:** n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
**Output:** 200
**Explanation:**
The graph is shown above.
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:**

![](https://assets.glich.co/dsa/cheapest-flights-within-k-stops/image2.png) 

**Input:** n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
**Output:** 500
**Explanation:**
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

**Constraints:**

* `1 <= n <= 100`
* `0 <= flights.length <= (n * (n - 1) / 2)`
* `flights[i].length == 3`
* `0 <= fromi, toi < n`
* `fromi != toi`
* `1 <= pricei <= 104`
* There will not be any multiple flights between two cities.
* `0 <= src, dst, k < n`
* `src != dst`

# Approaches
## Brute-Force Depth First Search
This is a straightforward recursive approach. We explore every possible path from the source `src` to the destination `dst`. We keep track of the number of stops and the cumulative cost along each path. If a path reaches the destination within the allowed `k` stops, we compare its cost with the minimum cost found so far and update it if necessary. To avoid getting stuck in cycles and exploring excessively long paths, we prune any path that exceeds `k` stops.
**Time:** O(n^(k+1)). In the worst case, the search tree can have a branching factor of up to `n-1` and a depth of `k+1`. · **Space:** O(k+n+E). The space is dominated by the recursion stack depth, which can go up to `k+1`, and the space for the adjacency list, which is `O(n+E)`.
**Pros:** Conceptually simple and easy to implement.
**Cons:** Extremely inefficient due to re-visiting nodes and exploring an exponential number of paths.; Will likely result in a Time Limit Exceeded (TLE) error on most competitive programming platforms for non-trivial inputs.
### Explanation
First, we represent the graph using an adjacency list, where `adj[i]` stores a list of pairs `(neighbor, price)` for all flights departing from city `i`.
We initialize a global variable `minCost` to a very large value.
We then start a recursive DFS from the source city. The DFS function `dfs(city, edges, cost)` takes the current city, the number of flights taken so far, and the current path cost as arguments. Note that `k` stops means a path can have at most `k+1` flights.
The base cases for the recursion are:
- If `edges > k + 1`, we have exceeded the flight limit.
- If the current `city` is the `dst`, we have found a valid route. We update `minCost = min(minCost, cost)`.
In the recursive step, we iterate through all the neighbors of the current city. For each neighbor, we make a recursive call, incrementing the edge count and adding the flight price to the cost.
A simple optimization is to prune a path if its current cost already exceeds `minCost`.
This approach is very slow because it may explore the same city multiple times through different paths, leading to an exponential time complexity.
```java
class Solution {
    int minCost = Integer.MAX_VALUE;
    List<int[]>[] adj;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] flight : flights) {
            adj[flight[0]].add(new int[]{flight[1], flight[2]});
        }

        // k stops means k+1 edges
        dfs(src, dst, k + 1, 0, 0);

        return minCost == Integer.MAX_VALUE ? -1 : minCost;
    }

    private void dfs(int u, int dst, int maxEdges, int edges, int cost) {
        if (edges > maxEdges) {
            return;
        }
        if (u == dst) {
            minCost = Math.min(minCost, cost);
            return;
        }

        for (int[] flight : adj[u]) {
            int v = flight[0];
            int price = flight[1];
            if (cost + price > minCost) { // Pruning
                continue;
            }
            dfs(v, dst, maxEdges, edges + 1, cost + price);
        }
    }
}
```
### Algorithm
1. Build an adjacency list representation of the graph where `adj[u]` contains pairs of `(v, price)` for each flight from `u` to `v`.
2. Initialize a global variable `minCost` to infinity.
3. Define a recursive function `dfs(u, dst, maxEdges, edges, cost)`.
4. Start the search by calling `dfs(src, dst, k + 1, 0, 0)`.
5. Inside `dfs`:
   a. If `edges > maxEdges`, prune the path as it has too many flights.
   b. If `u == dst`, a valid path is found. Update `minCost = min(minCost, cost)`.
   c. For each neighbor `v` of `u` with flight price `p`:
      i. If `cost + p > minCost`, prune this sub-path as it's not optimal.
      ii. Recursively call `dfs(v, dst, maxEdges, edges + 1, cost + p)`.
6. After the initial call returns, if `minCost` is still infinity, it means the destination is unreachable. Return -1, otherwise return `minCost`.

## Dijkstra's Algorithm with Stops
This problem can be modeled as a shortest path problem on an expanded state graph. A standard Dijkstra's algorithm finds the shortest path based only on cost, but here we also have a constraint on the number of stops. We can incorporate the number of stops into the state definition. The state in our search will be `(city, flights_taken)`. We use a priority queue to always explore the path with the minimum cost first.
**Time:** O(E*k + n*k*log(n*k)). The number of states is `n * (k+1)`. Each state is pushed to the priority queue. For each popped state, we iterate its neighbors. The complexity is dominated by priority queue operations on `n*k` states and relaxing `E*k` edges. · **Space:** O(n*k + E). `O(n*k)` for the `minCosts` array and the priority queue, and `O(n+E)` for the adjacency list.
**Pros:** Much more efficient than brute-force search.; Guaranteed to find the optimal solution due to the nature of Dijkstra's algorithm.
**Cons:** More complex to implement than a simple DFS or Bellman-Ford.; The time and space complexity depends on `k`, which can be large.
### Explanation
The state we'll use in our priority queue is a tuple `(cost, city, flights)`. The priority queue will be ordered by `cost`. A path with `k` stops has `k+1` flights.
We need to keep track of the minimum cost to reach each city with a specific number of flights to avoid cycles and redundant computations. A 2D array, `minCosts[city][flights]`, can be used for this purpose.
The algorithm proceeds as follows:
1. Build an adjacency list for the graph.
2. Initialize a priority queue and add the starting state: `{cost=0, city=src, flights=0}`.
3. Initialize the `minCosts` array with infinity. Set `minCosts[src][0] = 0`.
4. While the priority queue is not empty, extract the state `{cost, u, flights}` with the smallest `cost`.
5. If `u` is the destination `dst`, we have found the cheapest path that satisfies the stop constraint, so we can return `cost`. Dijkstra's nature ensures this is the first time we reach `dst` with the overall minimum cost.
6. If the number of `flights` is greater than `k+1`, we cannot continue this path.
7. For each neighbor `v` of `u`, we calculate the new cost and flights. If this new path to `v` (with `flights + 1`) is cheaper than any previously found path to `v` with the same number of flights, we update `minCosts[v][flights + 1]` and push the new state `{newCost, v, flights + 1}` to the priority queue.
This approach is much more efficient than brute-force DFS because it intelligently prunes search paths using costs and stop counts, guided by the priority queue.
```java
class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        List<int[]>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] flight : flights) {
            adj[flight[0]].add(new int[]{flight[1], flight[2]});
        }

        int[][] minCosts = new int[n][k + 2];
        for (int[] row : minCosts) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        // PQ stores {cost, city, flights_taken}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        
        pq.offer(new int[]{0, src, 0});
        minCosts[src][0] = 0;

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int cost = curr[0];
            int u = curr[1];
            int flights_taken = curr[2];

            if (u == dst) {
                return cost;
            }

            if (flights_taken > k) { // k stops means k+1 flights
                continue;
            }

            for (int[] neighbor : adj[u]) {
                int v = neighbor[0];
                int price = neighbor[1];
                
                if (cost + price < minCosts[v][flights_taken + 1]) {
                    minCosts[v][flights_taken + 1] = cost + price;
                    pq.offer(new int[]{cost + price, v, flights_taken + 1});
                }
            }
        }

        return -1;
    }
}
```
### Algorithm
1. Model the problem on a state graph where each node is a pair `(city, stops)`.
2. Build an adjacency list for the flight graph.
3. Use a priority queue to store `(cost, city, stops)`, prioritized by `cost`.
4. Use a 2D array `minCosts[n][k+2]` to store the minimum cost to reach a city with a certain number of flights. Initialize it with infinity.
5. Push the starting state `(0, src, 0)` into the priority queue, where 0 is the number of flights taken. `minCosts[src][0] = 0`.
6. While the priority queue is not empty:
   a. Pop the state with the minimum cost: `(cost, u, flights_taken)`.
   b. If `u == dst`, return `cost`.
   c. If `flights_taken > k`, this path has too many stops, so skip it.
   d. For each neighbor `v` of `u` with flight price `p`:
      i. Calculate the new state: `(cost + p, v, flights_taken + 1)`.
      ii. If `cost + p` is less than `minCosts[v][flights_taken + 1]`, it's a better path.
      iii. Update `minCosts[v][flights_taken + 1] = cost + p` and push the new state to the priority queue.
7. If the queue becomes empty and the destination was not reached, return -1.

## Bellman-Ford Based Dynamic Programming
This problem has an optimal substructure and overlapping subproblems, making it suitable for dynamic programming. The Bellman-Ford algorithm's structure is a natural fit. The standard Bellman-Ford algorithm finds the shortest paths from a source by iteratively relaxing all edges. After `i` iterations, it guarantees to find the shortest path containing at most `i` edges. We can adapt this to our problem, as "at most `k` stops" is equivalent to "at most `k+1` edges".
**Time:** O((k+1) * E), where `E` is the number of flights. We have an outer loop that runs `k+1` times and an inner loop that iterates through all `E` flights. · **Space:** O(n). We need two arrays of size `n` to store the costs for the current and previous iterations.
**Pros:** Generally more efficient than the Dijkstra-based approach for this problem.; Simple and clean implementation without complex data structures like priority queues.
**Cons:** May perform redundant work by iterating over all edges in every iteration, even those not on a promising path.
### Explanation
We'll use a 1D array, `costs`, where `costs[i]` stores the minimum cost to reach city `i` from the source `src`.
We initialize `costs[src]` to 0 and all other `costs[i]` to infinity.
We then run a loop `k+1` times. Each iteration `i` of this loop calculates the minimum costs for paths with at most `i` edges.
Inside the loop, we create a temporary copy of the `costs` array, say `tempCosts`. This is crucial because the calculations for paths of length `i` must be based on the results for paths of length `i-1`, not the partially updated results of length `i`.
We iterate through every flight `[u, v, price]`. If city `u` was reachable in the previous iteration (i.e., `costs[u]` is not infinity), we try to relax the edge to `v`. This means we update `tempCosts[v]` with `min(tempCosts[v], costs[u] + price)`.
After iterating through all flights, we copy `tempCosts` back to `costs`. This completes one iteration.
After `k+1` iterations, `costs[dst]` will hold the minimum cost to reach the destination with at most `k` stops. If it's still infinity, the destination is unreachable.
This approach is efficient and relatively simple to implement.
```java
class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // dist[i] = min cost to reach city i
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        // k stops means k+1 edges. We run k+1 iterations.
        for (int i = 0; i <= k; i++) {
            int[] temp = Arrays.copyOf(dist, n);
            for (int[] flight : flights) {
                int u = flight[0];
                int v = flight[1];
                int price = flight[2];
                if (dist[u] != Integer.MAX_VALUE) {
                    temp[v] = Math.min(temp[v], dist[u] + price);
                }
            }
            dist = temp;
        }

        return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
    }
}
```
### Algorithm
1. Create an array `costs` of size `n` to store the minimum cost to reach each city.
2. Initialize `costs[src] = 0` and all other elements to infinity.
3. Loop from `i = 0` to `k` (for `k+1` iterations, representing up to `k+1` edges).
   a. Create a temporary array `tempCosts` as a copy of `costs`.
   b. For each flight `[u, v, price]` in the `flights` array:
      i. If the source of the flight `u` is reachable (`costs[u]` is not infinity), update the cost to reach `v`: `tempCosts[v] = min(tempCosts[v], costs[u] + price)`.
   c. After checking all flights, update `costs` with `tempCosts`.
4. After the loop, `costs[dst]` contains the result. If it's infinity, return -1; otherwise, return the value.

# Solutions
### Java

```java
class Solution { private static final int INF = 0x3f3f3f3f ; public int findCheapestPrice ( int n , int [][] flights , int src , int dst , int k ) { int [] dist = new int [ n ]; int [] backup = new int [ n ]; Arrays . fill ( dist , INF ); dist [ src ] = 0 ; for ( int i = 0 ; i < k + 1 ; ++ i ) { System . arraycopy ( dist , 0 , backup , 0 , n ); for ( int [] e : flights ) { int f = e [ 0 ], t = e [ 1 ], p = e [ 2 ]; dist [ t ] = Math . min ( dist [ t ], backup [ f ] + p ); } } return dist [ dst ] == INF ? - 1 : dist [ dst ]; } }
```

### CPP

```cpp
class Solution { public: int findCheapestPrice ( int n , vector < vector < int >>& flights , int src , int dst , int k ) { const int inf = 0x3f3f3f3f ; vector < int > dist ( n , inf ); vector < int > backup ; dist [ src ] = 0 ; for ( int i = 0 ; i < k + 1 ; ++ i ) { backup = dist ; for ( auto & e : flights ) { int f = e [ 0 ], t = e [ 1 ], p = e [ 2 ]; dist [ t ] = min ( dist [ t ], backup [ f ] + p ); } } return dist [ dst ] == inf ? - 1 : dist [ dst ]; } };
```

### Python

```python
class Solution : def findCheapestPrice ( self , n : int , flights : List [ List [ int ]], src : int , dst : int , k : int ) -> int : INF = 0x3F3F3F3F dist = [ INF ] * n dist [ src ] = 0 for _ in range ( k + 1 ): backup = dist . copy () for f , t , p in flights : dist [ t ] = min ( dist [ t ], backup [ f ] + p ) return - 1 if dist [ dst ] == INF else dist [ dst ]
```