Sliding Puzzle
Description
You are given a network of n cities labeled from 0 to n - 1. You are also given an array flights where flights[i] = [from_i, to_i, price_i] indicates there is a one-way flight from city from_i to city to_i with cost price_i.
You are additionally 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.
A "stop" is any intermediate city along the path — the source and destination themselves do not count as stops.
Examples
Example 1
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: There are 4 cities and 5 flights. We want the cheapest way from city 0 to city 3 with at most 1 stop.
- Path 0 → 1 → 3 costs 100 + 600 = 700 and uses 1 stop (at city 1). This is valid.
- Path 0 → 1 → 2 → 3 costs 100 + 100 + 200 = 400 but uses 2 stops (at cities 1 and 2). This exceeds the limit of k = 1 stop, so it is invalid.
The cheapest valid path costs 700.
Example 2
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: There are 3 cities and 3 flights. We want the cheapest way from city 0 to city 2 with at most 1 stop.
- Direct flight 0 → 2 costs 500 (0 stops).
- Path 0 → 1 → 2 costs 100 + 100 = 200 (1 stop at city 1).
The cheaper option is 200 via the 1-stop path.
Example 3
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation: Same flight network as Example 2, but now k = 0 — we cannot make any stops. The only option is the direct flight 0 → 2 costing 500. The path 0 → 1 → 2 would be cheaper at 200, but it requires 1 stop, which exceeds k = 0.
Constraints
- 1 ≤ n ≤ 100
- 0 ≤ flights.length ≤ n × (n - 1) / 2
- flights[i].length == 3
- 0 ≤ from_i, to_i < n
- from_i ≠ to_i
- 1 ≤ price_i ≤ 10^4
- There will not be any multiple flights between two cities.
- 0 ≤ src, dst, k < n
- src ≠ dst
Editorial
Brute Force
Intuition
The most straightforward way to find the cheapest flight route is to try every possible path from the source to the destination and keep track of the minimum cost among all valid paths.
Imagine you are at an airport with a map of all available flights. You start at city src and want to reach city dst. You could systematically try every combination of flights: take the first available flight, then from that city try every onward flight, and so on. Every time you reach the destination, you note down the total cost. After exhausting all possibilities, you pick the cheapest one.
This is exactly what Depth-First Search (DFS) does — it explores each path to its end before backtracking to try alternatives. We add one important constraint: we stop exploring a path if we have already used more than k stops, since any further extension would be invalid. We also prune paths whose running cost already exceeds our current best answer, since they cannot improve the result.
Step-by-Step Explanation
Let's trace through Example 2: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1.
First, build the adjacency list:
- City 0 → [(1, 100), (2, 500)]
- City 1 → [(2, 100)]
Step 1: Start DFS from source node 0. Current cost = 0, stops remaining = 1, best_cost = ∞.
Step 2: From node 0, pick the first flight: 0 → 1 with cost 100. New cost = 0 + 100 = 100. Stops remaining decreases to 0.
Step 3: Arrive at node 1 with cost 100. Node 1 is not the destination, so explore its neighbors. Stops remaining = 0, so this is our last allowed flight.
Step 4: From node 1, take flight 1 → 2 with cost 100. New cost = 100 + 100 = 200. Node 2 is the destination! Record best_cost = 200.
Step 5: Backtrack all the way to node 0. We have found one valid path costing 200.
Step 6: From node 0, try the second flight: 0 → 2 with cost 500. New cost = 0 + 500 = 500. Node 2 is the destination!
Step 7: Compare 500 with best_cost = 200. Since 500 > 200, this path is worse. best_cost remains 200.
Step 8: All paths from source explored. Return best_cost = 200.
DFS — Exploring All Paths from Source to Destination — Watch how DFS exhaustively explores every possible flight path, backtracking when reaching the destination or exceeding the stop limit, and keeps the cheapest valid route.
Algorithm
- Build an adjacency list from the flights array
- Initialize best_cost = ∞
- Run DFS starting from
srcwithkstops remaining and cost = 0:- If current node ==
dst, update best_cost = min(best_cost, current_cost). Return. - If stops remaining < 0, return (exceeded stop limit).
- For each neighbor (next, price) of the current node:
- If current_cost + price < best_cost (pruning), recurse with (next, stops - 1, current_cost + price)
- If current node ==
- Return best_cost if it was updated, otherwise return -1
Code
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<vector<pair<int,int>>> adj(n);
for (auto& f : flights) {
adj[f[0]].push_back({f[1], f[2]});
}
int result = INT_MAX;
dfs(adj, src, dst, k, 0, result);
return result == INT_MAX ? -1 : result;
}
void dfs(vector<vector<pair<int,int>>>& adj, int node, int dst,
int stops, int cost, int& result) {
if (node == dst) {
result = min(result, cost);
return;
}
if (stops < 0) return;
for (auto& [next, price] : adj[node]) {
if (cost + price < result) {
dfs(adj, next, dst, stops - 1, cost + price, result);
}
}
}
};class Solution:
def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
adj = defaultdict(list)
for u, v, w in flights:
adj[u].append((v, w))
self.best = float('inf')
def dfs(node, stops, cost):
if node == dst:
self.best = min(self.best, cost)
return
if stops < 0:
return
for next_node, price in adj[node]:
if cost + price < self.best:
dfs(next_node, stops - 1, cost + price)
dfs(src, k, 0)
return self.best if self.best != float('inf') else -1class Solution {
private int best = Integer.MAX_VALUE;
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[] f : flights) adj[f[0]].add(new int[]{f[1], f[2]});
dfs(adj, src, dst, k, 0);
return best == Integer.MAX_VALUE ? -1 : best;
}
private void dfs(List<int[]>[] adj, int node, int dst, int stops, int cost) {
if (node == dst) {
best = Math.min(best, cost);
return;
}
if (stops < 0) return;
for (int[] next : adj[node]) {
if (cost + next[1] < best) {
dfs(adj, next[0], dst, stops - 1, cost + next[1]);
}
}
}
}Complexity Analysis
Time Complexity: O(n^(k+1))
In the worst case (a complete directed graph), from each city we can fly to up to n - 1 other cities. We explore paths up to depth k + 1 (since k stops means k + 1 flights). This creates a branching factor of up to n - 1 at each level, yielding O(n^(k+1)) paths to explore. Pruning helps in practice but does not improve the worst-case bound.
Space Complexity: O(k)
The recursion stack depth is at most k + 1, since we stop recurring once stops drop below 0. The adjacency list uses O(V + E) space, but the dominant concern is the recursion depth, which is O(k).
Why This Approach Is Not Efficient
The DFS brute force has exponential time complexity: O(n^(k+1)). With n up to 100 cities and k up to 99 stops, the worst case could explore up to 100^100 paths — an astronomically large number that no computer can handle.
The core inefficiency lies in redundant work: DFS may visit the same city multiple times through different paths at the same depth, without remembering the cheapest cost it has already found to reach that city. For instance, if there are 5 different paths to reach city X with 2 stops remaining, DFS explores all onward routes from city X five separate times — even though only the cheapest arrival at X matters for finding the optimal answer.
Key insight: instead of exploring paths one-by-one from source to destination (top-down), we can propagate cheapest costs outward from the source, level by level. Each "level" represents one additional flight taken. By processing all cities at a given depth before going deeper, we avoid revisiting the same subproblems and naturally respect the stop limit.
Better Approach - BFS Level-by-Level
Intuition
Instead of diving deep into one path at a time like DFS, we can spread outward from the source city like ripples on a pond. In the first "wave," we discover all cities reachable by exactly one flight. In the second wave, we extend those to find cities reachable with one stop. We continue for at most k + 1 waves (since k stops means k + 1 flights).
This is Breadth-First Search (BFS). We use a queue to process cities level by level. At each level, for every city in the current queue, we check all outgoing flights and update the cheapest known cost to reach each neighbor. If the new cost is cheaper, we enqueue that neighbor for the next level.
The crucial advantage over DFS: BFS processes each "depth" completely before moving to the next. This means we naturally stop after k + 1 levels without needing recursion or backtracking. We also maintain a distance array that remembers the best cost found so far for each city, avoiding redundant exploration.
Step-by-Step Explanation
Let's trace through Example 2: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1.
Adjacency list: 0 → [(1,100),(2,500)], 1 → [(2,100)]
Step 1: Initialize dist = [0, ∞, ∞]. Enqueue source node 0 with cost 0.
Step 2: Level 0 (direct flights from source) — Dequeue node 0 with cost 0. Explore its outgoing flights.
Step 3: Relax edge 0 → 1: new cost = 0 + 100 = 100. Since 100 < ∞, update dist[1] = 100. Enqueue (1, 100).
Step 4: Relax edge 0 → 2: new cost = 0 + 500 = 500. Since 500 < ∞, update dist[2] = 500. Enqueue (2, 500).
Step 5: Level 0 complete. After direct flights: dist = [0, 100, 500]. Start Level 1 (paths with 1 stop).
Step 6: Dequeue node 1 with cost 100. Explore flight 1 → 2: new cost = 100 + 100 = 200. Since 200 < 500, update dist[2] = 200.
Step 7: Dequeue node 2 with cost 500. No outgoing flights from node 2.
Step 8: Level 1 complete. We have used k = 1 stop. dist[2] = 200. Return 200.
BFS Level-by-Level — Propagating Cheapest Costs Outward — Watch how BFS spreads from the source node level by level, discovering cheaper routes at each depth, and naturally stops after k+1 levels.
Algorithm
- Build an adjacency list from the flights array
- Initialize dist array: dist[src] = 0, all others = ∞
- Create a queue and enqueue (src, 0)
- Set stops = 0
- While queue is not empty AND stops ≤ k:
- Record the current queue size (level_size)
- For each of the level_size entries:
- Dequeue (node, cost)
- For each neighbor (next, price) of node:
- If cost + price < dist[next], update dist[next] and enqueue (next, cost + price)
- Increment stops
- Return dist[dst] if reachable, otherwise -1
Code
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<vector<pair<int,int>>> adj(n);
for (auto& f : flights) {
adj[f[0]].push_back({f[1], f[2]});
}
vector<int> dist(n, INT_MAX);
dist[src] = 0;
queue<pair<int,int>> q;
q.push({src, 0});
int stops = 0;
while (!q.empty() && stops <= k) {
int sz = q.size();
while (sz--) {
auto [node, cost] = q.front();
q.pop();
for (auto& [next, price] : adj[node]) {
if (cost + price < dist[next]) {
dist[next] = cost + price;
q.push({next, dist[next]});
}
}
}
stops++;
}
return dist[dst] == INT_MAX ? -1 : dist[dst];
}
};class Solution:
def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
adj = defaultdict(list)
for u, v, w in flights:
adj[u].append((v, w))
dist = [float('inf')] * n
dist[src] = 0
queue = deque([(src, 0)])
stops = 0
while queue and stops <= k:
level_size = len(queue)
for _ in range(level_size):
node, cost = queue.popleft()
for next_node, price in adj[node]:
new_cost = cost + price
if new_cost < dist[next_node]:
dist[next_node] = new_cost
queue.append((next_node, new_cost))
stops += 1
return dist[dst] if dist[dst] != float('inf') else -1class 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[] f : flights) adj[f[0]].add(new int[]{f[1], f[2]});
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{src, 0});
int stops = 0;
while (!queue.isEmpty() && stops <= k) {
int sz = queue.size();
while (sz-- > 0) {
int[] curr = queue.poll();
int node = curr[0], cost = curr[1];
for (int[] next : adj[node]) {
int newCost = cost + next[1];
if (newCost < dist[next[0]]) {
dist[next[0]] = newCost;
queue.offer(new int[]{next[0], newCost});
}
}
}
stops++;
}
return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}
}Complexity Analysis
Time Complexity: O((V + E) × K)
We process at most k + 1 levels. In each level, we dequeue every node currently in the queue and examine its outgoing edges. In the worst case, each edge may be considered once per level, giving O(E) work per level. Across all levels: O(E × K). Building the adjacency list adds O(V + E). Total: O((V + E) × K).
Space Complexity: O(V × K)
The dist array uses O(V) space. The adjacency list uses O(V + E). The queue can hold up to O(V) entries per level, and across k levels a node may be enqueued multiple times (once per level where its cost improves). In the worst case, the queue holds O(V × K) entries. This is the dominant term.
Why This Approach Is Not Efficient
BFS is a dramatic improvement over DFS — it moves from exponential O(n^(k+1)) to polynomial O((V + E) × K). However, it still has practical overhead that can be reduced.
The main issues with BFS for this problem:
-
Redundant queue entries: A node can be enqueued multiple times at the same level if it is reachable via several paths. This means we may process the same city multiple times, relaxing its outgoing edges redundantly. In dense flight networks, the queue can grow significantly.
-
Adjacency list overhead: BFS requires constructing and maintaining an adjacency list, which uses O(V + E) extra memory and O(E) build time.
-
Queue management: Enqueue and dequeue operations, while O(1) each, add constant-factor overhead for every edge relaxation.
Key insight: we can eliminate the adjacency list entirely by iterating directly over the flights array. Instead of processing nodes and their neighbors, we process all edges in bulk for each iteration. This is exactly what the Bellman-Ford algorithm does — it achieves the same O(E × K) time complexity with simpler code, lower constant factors, and only O(V) space.
Optimal Approach - Bellman-Ford with K+1 Iterations
Intuition
The Bellman-Ford algorithm is traditionally used to find shortest paths in a weighted graph. Its core idea is simple: repeatedly "relax" all edges, and after enough repetitions, the shortest distances will have propagated to all reachable nodes.
Here is the key insight for this problem: each iteration of Bellman-Ford extends paths by exactly one more edge. After 1 iteration, we know the cheapest way to reach each city using exactly 1 flight (0 stops). After 2 iterations, we know the cheapest way using up to 2 flights (1 stop). After k + 1 iterations, we know the cheapest way using up to k + 1 flights (k stops) — which is exactly what the problem asks for.
There is one critical detail: during each iteration, we must use a backup copy of the distances from the previous iteration. Without this, updating dist[A] early in the iteration and then using dist[A] to update dist[B] later in the same iteration effectively allows a two-edge extension in a single pass. The backup ensures we only extend paths by one edge per iteration, correctly enforcing the stop limit.
Think of it like a relay race with k + 1 rounds. In each round, every runner checks: can I pass the baton more cheaply than the current record? After k + 1 rounds, we have the cheapest possible relay from start to finish.
Step-by-Step Explanation
Let's trace through Example 2: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1.
Step 1: Initialize dist = [0, ∞, ∞]. Source has cost 0, all other cities are unreachable.
Step 2: Iteration 1 — Create backup = [0, ∞, ∞]. This snapshot ensures we only extend paths by one edge.
Step 3: Process flight [0,1,100]: backup[0] + 100 = 0 + 100 = 100. Since 100 < ∞, update dist[1] = 100.
Step 4: Process flight [1,2,100]: backup[1] = ∞ (city 1 was not reachable in the backup). Cannot use this flight yet. Skip.
Step 5: Process flight [0,2,500]: backup[0] + 500 = 0 + 500 = 500. Since 500 < ∞, update dist[2] = 500.
Step 6: After iteration 1: dist = [0, 100, 500]. These are the cheapest costs using at most 1 flight (0 stops).
Step 7: Iteration 2 — Create backup = [0, 100, 500].
Step 8: Process flight [0,1,100]: backup[0] + 100 = 100 = dist[1]. No improvement.
Step 9: Process flight [1,2,100]: backup[1] + 100 = 100 + 100 = 200. Since 200 < 500, update dist[2] = 200. The 1-stop route is cheaper!
Step 10: Process flight [0,2,500]: backup[0] + 500 = 500 > 200. No improvement.
Step 11: After iteration 2: dist = [0, 100, 200]. Return dist[2] = 200.
Bellman-Ford — Relaxing All Edges Iteration by Iteration — Watch how Bellman-Ford relaxes every flight in each iteration, using a backup array to ensure paths extend by exactly one edge per pass, until the cheapest route within k stops is found.
Algorithm
- Initialize dist array of size n with ∞ for all cities except dist[src] = 0
- For i from 0 to k (inclusive), i.e., k + 1 iterations:
- Create a backup copy of the current dist array
- For each flight [from, to, price]:
- If backup[from] ≠ ∞ and backup[from] + price < dist[to]:
- Update dist[to] = backup[from] + price
- If backup[from] ≠ ∞ and backup[from] + price < dist[to]:
- Return dist[dst] if it is not ∞, otherwise return -1
Code
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<int> dist(n, INT_MAX);
dist[src] = 0;
for (int i = 0; i <= k; i++) {
vector<int> backup = dist;
for (auto& f : flights) {
int u = f[0], v = f[1], w = f[2];
if (backup[u] != INT_MAX) {
dist[v] = min(dist[v], backup[u] + w);
}
}
}
return dist[dst] == INT_MAX ? -1 : dist[dst];
}
};class Solution:
def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
dist = [float('inf')] * n
dist[src] = 0
for _ in range(k + 1):
backup = dist.copy()
for u, v, w in flights:
if backup[u] != float('inf'):
dist[v] = min(dist[v], backup[u] + w)
return dist[dst] if dist[dst] != float('inf') else -1class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 0; i <= k; i++) {
int[] backup = dist.clone();
for (int[] f : flights) {
int u = f[0], v = f[1], w = f[2];
if (backup[u] != Integer.MAX_VALUE) {
dist[v] = Math.min(dist[v], backup[u] + w);
}
}
}
return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}
}Complexity Analysis
Time Complexity: O((K + 1) × E)
We run exactly k + 1 iterations. In each iteration, we copy the dist array (O(V)) and then iterate over all E flights to relax edges (O(E)). Total: O((K + 1) × (V + E)). Since E ≥ V - 1 in a connected graph, this simplifies to O((K + 1) × E) or O(K × E).
For the given constraints: k ≤ 99, E ≤ n × (n - 1) / 2 ≤ 4950, so at most 100 × 4950 ≈ 500,000 operations — very fast.
Space Complexity: O(V)
We maintain two arrays: dist and backup, each of size n. No adjacency list is needed — we iterate directly over the flights array. Total space: O(V), which is optimal since we need at least O(V) to store distances.