Cheapest Flights Within K Stops

🎯

Cheapest Flights Within K Stops

mediumDPAmazonGoogleFacebook

Imagine you are planning a trip and want to find the cheapest flight route from your home city to a destination city, but you want to limit the number of stops you make along the way to save time and hassle.

💡 This problem is about finding the minimum cost path in a graph with a constraint on the number of stops. Beginners often struggle because it looks like a shortest path problem but the stop constraint makes classic algorithms like Dijkstra insufficient, requiring dynamic programming or Bellman-Ford style approaches.

📋

Problem Statement

Given n cities numbered from 0 to n-1 and a list of flights where each flight is represented as (source, destination, price), find the cheapest price from a given source city to a destination city with at most K stops. If no such route exists, return -1. Input: - n: integer, number of cities - flights: list of tuples (src, dst, price) - src: integer, starting city - dst: integer, destination city - K: integer, maximum number of stops allowed Output: - integer, minimum cost to reach dst from src with at most K stops, or -1 if impossible.

1 ≤ n ≤ 10^50 ≤ flights.length ≤ 10^50 ≤ price ≤ 10^40 ≤ src, dst < n0 ≤ K < n

💡

Example

Input"n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, K = 1"

Output200

The cheapest route from 0 to 2 with at most 1 stop is 0 -> 1 -> 2 with cost 100 + 100 = 200.

• No flights available → output -1
• Source equals destination → output 0
• K = 0 and direct flight exists → output direct flight cost
• K = 0 and no direct flight → output -1

🔁

Why DP?

Why greedy fails:

A greedy approach that always picks the cheapest immediate flight can fail because a slightly more expensive immediate flight might lead to a cheaper overall route within K stops. For example, choosing a direct flight costing 500 is greedy but 0->1->2 costing 200 is cheaper but requires considering multiple steps.

DP state:

dp[i][j] represents the minimum cost to reach city j using at most i flights (i.e., i-1 stops).

Recurrence:dp[i][v] = min(dp[i][v], dp[i-1][u] + cost(u,v)) for all edges (u,v)

The cost to reach city v with i flights is the minimum of its current cost and the cost to reach u with i-1 flights plus the cost from u to v.

⚠️

Common Mistakes

Not pruning paths exceeding K stops in brute force

Leads to infinite recursion or TLE

✅ Add condition to stop recursion when stops exceed K+1

Overwriting dp array in bottom-up DP leading to incorrect results

Incorrect minimum costs due to using updated values in same iteration

✅ Use separate arrays or copy previous row before updates

Using Dijkstra without modification ignoring stop constraints

Returns incorrect results because it doesn't limit stops

✅ Use DP or Bellman-Ford variant that tracks stops explicitly

Not handling case when source equals destination

Returns -1 instead of 0

✅ Add base case to return 0 if src == dst

Using large infinity values causing integer overflow

Incorrect comparisons or overflow errors

✅ Use safe large values like Integer.MAX_VALUE/2 or float('inf')

🧠

Brute Force (DFS with Stops Limit)

💡 This approach tries all possible flight paths up to K stops recursively. It is the foundation to understand the problem but is inefficient due to repeated computations.

Intuition

Try every possible flight path from source to destination with at most K stops, keeping track of the cost and updating the minimum.

Algorithm

1. Start DFS from source city with 0 stops and 0 cost.
2. At each city, if destination reached, update minimum cost.
3. If stops exceed K, backtrack.
4. Explore all outgoing flights recursively.

💡 The recursion tree grows exponentially because each city can lead to multiple next cities, making it hard to track all paths without pruning.

Recurrence:cost(city, stops) = min over all next cities { cost(next_city, stops+1) + flight_cost }

</>

Code

from collections import defaultdict
import sys

def findCheapestPrice(n, flights, src, dst, K):
    graph = defaultdict(list)
    for u,v,w in flights:
        graph[u].append((v,w))
    min_cost = [sys.maxsize]
    def dfs(city, stops, cost):
        if stops > K + 1 or cost > min_cost[0]:
            return
        if city == dst:
            min_cost[0] = cost
            return
        for nei, price in graph[city]:
            dfs(nei, stops + 1, cost + price)
    dfs(src, 0, 0)
    return min_cost[0] if min_cost[0] != sys.maxsize else -1

# Example usage
if __name__ == '__main__':
    n = 3
    flights = [[0,1,100],[1,2,100],[0,2,500]]
    src = 0
    dst = 2
    K = 1
    print(findCheapestPrice(n, flights, src, dst, K))  # Output: 200

Line Notes

graph = defaultdict(list)Build adjacency list for quick access to neighbors

for u,v,w in flightsPopulate graph edges with costs

min_cost = [sys.maxsize]Use list to allow modification inside dfs closure

if stops > K + 1 or cost > min_cost[0]Prune paths exceeding stops or already more expensive

if city == dstUpdate minimum cost when destination reached

for nei, price in graph[city]Explore all neighbors recursively

dfs(src, 0, 0)Start DFS from source with zero stops and cost

import java.util.*;

public class Solution {
    private int minCost = Integer.MAX_VALUE;
    private Map<Integer, List<int[]>> graph = new HashMap<>();
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        for (int[] f : flights) {
            graph.computeIfAbsent(f[0], k -> new ArrayList<>()).add(new int[]{f[1], f[2]});
        }
        dfs(src, dst, K + 1, 0);
        return minCost == Integer.MAX_VALUE ? -1 : minCost;
    }
    private void dfs(int city, int dst, int stops, int cost) {
        if (stops < 0 || cost > minCost) return;
        if (city == dst) {
            minCost = cost;
            return;
        }
        if (!graph.containsKey(city)) return;
        for (int[] next : graph.get(city)) {
            dfs(next[0], dst, stops - 1, cost + next[1]);
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int n = 3;
        int[][] flights = {{0,1,100},{1,2,100},{0,2,500}};
        int src = 0, dst = 2, K = 1;
        System.out.println(sol.findCheapestPrice(n, flights, src, dst, K)); // 200
    }
}

Line Notes

private int minCost = Integer.MAX_VALUE;Track minimum cost globally

graph.computeIfAbsent(f[0], k -> new ArrayList<>())Build adjacency list

dfs(src, dst, K + 1, 0);Start DFS with allowed flights = K+1

if (stops < 0 || cost > minCost) return;Prune invalid or expensive paths

if (city == dst)Update minCost when destination reached

for (int[] next : graph.get(city))Explore neighbors recursively

public static void mainDriver code to test example

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;

class Solution {
    int minCost = INT_MAX;
    unordered_map<int, vector<pair<int,int>>> graph;
    void dfs(int city, int dst, int stops, int cost) {
        if (stops < 0 || cost > minCost) return;
        if (city == dst) {
            minCost = cost;
            return;
        }
        if (graph.find(city) == graph.end()) return;
        for (auto &next : graph[city]) {
            dfs(next.first, dst, stops - 1, cost + next.second);
        }
    }
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        for (auto &f : flights) {
            graph[f[0]].push_back({f[1], f[2]});
        }
        dfs(src, dst, K + 1, 0);
        return minCost == INT_MAX ? -1 : minCost;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> flights = {{0,1,100},{1,2,100},{0,2,500}};
    cout << sol.findCheapestPrice(3, flights, 0, 2, 1) << endl; // 200
    return 0;
}

Line Notes

unordered_map<int, vector<pair<int,int>>> graph;Adjacency list for flights

if (stops < 0 || cost > minCost) return;Prune invalid or costly paths

if (city == dst)Update minCost when destination reached

for (auto &next : graph[city])Explore all neighbors recursively

dfs(src, dst, K + 1, 0);Start DFS with K+1 flights allowed

return minCost == INT_MAX ? -1 : minCost;Return -1 if no route found

function findCheapestPrice(n, flights, src, dst, K) {
    const graph = new Map();
    for (const [u,v,w] of flights) {
        if (!graph.has(u)) graph.set(u, []);
        graph.get(u).push([v,w]);
    }
    let minCost = Infinity;
    function dfs(city, stops, cost) {
        if (stops > K + 1 || cost > minCost) return;
        if (city === dst) {
            minCost = cost;
            return;
        }
        if (!graph.has(city)) return;
        for (const [next, price] of graph.get(city)) {
            dfs(next, stops + 1, cost + price);
        }
    }
    dfs(src, 0, 0);
    return minCost === Infinity ? -1 : minCost;
}

// Example usage
console.log(findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1)); // 200

Line Notes

const graph = new Map();Build adjacency list for flights

if (!graph.has(u)) graph.set(u, []);Initialize adjacency list entry

let minCost = Infinity;Track minimum cost globally

if (stops > K + 1 || cost > minCost) return;Prune invalid or expensive paths

if (city === dst)Update minCost when destination reached

for (const [next, price] of graph.get(city))Explore neighbors recursively

dfs(src, 0, 0);Start DFS from source

⏱

Complexity

TimeO(n^(K+1))

SpaceO(n) for recursion stack

Each city can lead to multiple next cities, and recursion depth is up to K+1 flights, leading to exponential paths.

💡 For n=3 and K=1, this means exploring up to 3^2=9 paths, which is manageable, but for larger n and K it quickly becomes infeasible.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and build towards DP.

🧠

Top-Down DP with Memoization

💡 Memoization caches results of subproblems to avoid recomputation, improving brute force DFS to polynomial time.

Intuition

Store the cheapest cost to reach a city with a given number of stops to avoid recomputing the same states multiple times.

Algorithm

1. Build adjacency list from flights.
2. Define recursive function with parameters city and remaining stops.
3. If city is destination, return 0 cost.
4. If no stops left and city not destination, return infinity.
5. For each neighbor, recursively compute cost with one less stop and add flight cost.
6. Memoize and return minimum cost found.

💡 Memoization reduces exponential recursion to polynomial by caching results for each city and stops left.

Recurrence:dp(city, stops) = min over neighbors { cost(neighbor, stops-1) + flight_cost }

</>

Code

from collections import defaultdict
import sys

def findCheapestPrice(n, flights, src, dst, K):
    graph = defaultdict(list)
    for u,v,w in flights:
        graph[u].append((v,w))
    memo = {}
    def dp(city, stops):
        if city == dst:
            return 0
        if stops < 0:
            return sys.maxsize
        if (city, stops) in memo:
            return memo[(city, stops)]
        min_cost = sys.maxsize
        for nei, price in graph[city]:
            cost = dp(nei, stops - 1)
            if cost != sys.maxsize:
                min_cost = min(min_cost, cost + price)
        memo[(city, stops)] = min_cost
        return min_cost
    res = dp(src, K)
    return res if res != sys.maxsize else -1

# Example usage
if __name__ == '__main__':
    n = 3
    flights = [[0,1,100],[1,2,100],[0,2,500]]
    src = 0
    dst = 2
    K = 1
    print(findCheapestPrice(n, flights, src, dst, K))  # Output: 200

Line Notes

memo = {}Cache results for (city, stops) to avoid recomputation

if city == dstBase case: cost zero if destination reached

if stops < 0No stops left means no valid path

if (city, stops) in memoReturn cached result if available

for nei, price in graph[city]Try all neighbors to find minimum cost

memo[(city, stops)] = min_costStore computed minimum cost

return min_costReturn minimum cost for current state

import java.util.*;

public class Solution {
    private Map<String, Integer> memo = new HashMap<>();
    private Map<Integer, List<int[]>> graph = new HashMap<>();
    private int dst;
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        this.dst = dst;
        for (int[] f : flights) {
            graph.computeIfAbsent(f[0], k -> new ArrayList<>()).add(new int[]{f[1], f[2]});
        }
        int res = dp(src, K);
        return res == Integer.MAX_VALUE ? -1 : res;
    }
    private int dp(int city, int stops) {
        if (city == dst) return 0;
        if (stops < 0) return Integer.MAX_VALUE;
        String key = city + "," + stops;
        if (memo.containsKey(key)) return memo.get(key);
        int minCost = Integer.MAX_VALUE;
        if (!graph.containsKey(city)) {
            memo.put(key, minCost);
            return minCost;
        }
        for (int[] next : graph.get(city)) {
            int cost = dp(next[0], stops - 1);
            if (cost != Integer.MAX_VALUE) {
                minCost = Math.min(minCost, cost + next[1]);
            }
        }
        memo.put(key, minCost);
        return minCost;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int n = 3;
        int[][] flights = {{0,1,100},{1,2,100},{0,2,500}};
        int src = 0, dst = 2, K = 1;
        System.out.println(sol.findCheapestPrice(n, flights, src, dst, K)); // 200
    }
}

Line Notes

private Map<String, Integer> memo = new HashMap<>();Cache results for (city, stops)

if (city == dst) return 0;Base case: destination reached

if (stops < 0) return Integer.MAX_VALUE;No stops left means invalid path

String key = city + "," + stops;Create unique key for memoization

if (memo.containsKey(key)) return memo.get(key);Return cached result if available

for (int[] next : graph.get(city))Try all neighbors to find minimum cost

memo.put(key, minCost);Store computed minimum cost

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;

class Solution {
    unordered_map<int, vector<pair<int,int>>> graph;
    unordered_map<string, int> memo;
    int dst;
    int dp(int city, int stops) {
        if (city == dst) return 0;
        if (stops < 0) return INT_MAX;
        string key = to_string(city) + "," + to_string(stops);
        if (memo.count(key)) return memo[key];
        int minCost = INT_MAX;
        if (graph.find(city) == graph.end()) {
            memo[key] = minCost;
            return minCost;
        }
        for (auto &next : graph[city]) {
            int cost = dp(next.first, stops - 1);
            if (cost != INT_MAX && cost + next.second < minCost) {
                minCost = cost + next.second;
            }
        }
        memo[key] = minCost;
        return minCost;
    }
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        this->dst = dst;
        for (auto &f : flights) {
            graph[f[0]].push_back({f[1], f[2]});
        }
        int res = dp(src, K);
        return res == INT_MAX ? -1 : res;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> flights = {{0,1,100},{1,2,100},{0,2,500}};
    cout << sol.findCheapestPrice(3, flights, 0, 2, 1) << endl; // 200
    return 0;
}

Line Notes

unordered_map<string, int> memo;Cache results for (city, stops)

if (city == dst) return 0;Base case: destination reached

if (stops < 0) return INT_MAX;No stops left means invalid path

string key = to_string(city) + "," + to_string(stops);Unique key for memoization

if (memo.count(key)) return memo[key];Return cached result if available

for (auto &next : graph[city])Try all neighbors to find minimum cost

memo[key] = minCost;Store computed minimum cost

function findCheapestPrice(n, flights, src, dst, K) {
    const graph = new Map();
    for (const [u,v,w] of flights) {
        if (!graph.has(u)) graph.set(u, []);
        graph.get(u).push([v,w]);
    }
    const memo = new Map();
    function dp(city, stops) {
        if (city === dst) return 0;
        if (stops < 0) return Infinity;
        const key = city + ',' + stops;
        if (memo.has(key)) return memo.get(key);
        let minCost = Infinity;
        if (!graph.has(city)) {
            memo.set(key, minCost);
            return minCost;
        }
        for (const [next, price] of graph.get(city)) {
            const cost = dp(next, stops - 1);
            if (cost !== Infinity) {
                minCost = Math.min(minCost, cost + price);
            }
        }
        memo.set(key, minCost);
        return minCost;
    }
    const res = dp(src, K);
    return res === Infinity ? -1 : res;
}

// Example usage
console.log(findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1)); // 200

Line Notes

const memo = new Map();Cache results for (city, stops)

if (city === dst) return 0;Base case: destination reached

if (stops < 0) return Infinity;No stops left means invalid path

const key = city + ',' + stops;Unique key for memoization

if (memo.has(key)) return memo.get(key);Return cached result if available

for (const [next, price] of graph.get(city))Try all neighbors to find minimum cost

memo.set(key, minCost);Store computed minimum cost

⏱

Complexity

TimeO(n * K * E) where E is number of edges

SpaceO(n * K) for memoization

Each state (city, stops) is computed once, and for each state we explore edges.

💡 For n=3, K=1, and E=3, this means about 3*1*3=9 computations, much better than brute force.

Interview Verdict: Accepted

This approach is efficient enough for medium constraints and demonstrates DP memoization well.

🧠

Bottom-Up DP (Bellman-Ford Variant)

💡 This approach uses iterative DP similar to Bellman-Ford to find shortest paths with at most K stops, avoiding recursion and memo overhead.

Intuition

Build a DP table where dp[i][v] is the cheapest cost to reach city v using at most i flights, updating costs iteratively for each number of flights.

Algorithm

1. Initialize dp array with infinity, dp[0][src] = 0.
2. For i from 1 to K+1, copy dp[i-1] to dp[i] to start with previous costs.
3. For each flight (u,v,w), update dp[i][v] = min(dp[i][v], dp[i-1][u] + w).
4. After filling dp, answer is dp[K+1][dst] or -1 if unreachable.

💡 We iteratively improve the cost to reach each city with increasing number of flights, ensuring no invalid overwrites by using separate rows.

Recurrence:dp[i][v] = min(dp[i][v], dp[i-1][u] + cost(u,v))

</>

Code

def findCheapestPrice(n, flights, src, dst, K):
    INF = float('inf')
    dp = [[INF] * n for _ in range(K + 2)]
    dp[0][src] = 0
    for i in range(1, K + 2):
        dp[i] = dp[i-1][:]  # copy previous row
        for u, v, w in flights:
            if dp[i-1][u] != INF:
                dp[i][v] = min(dp[i][v], dp[i-1][u] + w)
    return dp[K+1][dst] if dp[K+1][dst] != INF else -1

# Example usage
if __name__ == '__main__':
    n = 3
    flights = [[0,1,100],[1,2,100],[0,2,500]]
    src = 0
    dst = 2
    K = 1
    print(findCheapestPrice(n, flights, src, dst, K))  # Output: 200

Line Notes

dp = [[INF] * n for _ in range(K + 2)]Create DP table for up to K+1 flights

dp[0][src] = 0Cost to reach source with 0 flights is zero

dp[i] = dp[i-1][:]Copy previous costs to start iteration

for u, v, w in flightsRelax edges for current number of flights

dp[i][v] = min(dp[i][v], dp[i-1][u] + w)Update minimum cost to reach city v

import java.util.*;

public class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        int INF = Integer.MAX_VALUE / 2;
        int[][] dp = new int[K + 2][n];
        for (int i = 0; i <= K + 1; i++) Arrays.fill(dp[i], INF);
        dp[0][src] = 0;
        for (int i = 1; i <= K + 1; i++) {
            dp[i] = dp[i - 1].clone();
            for (int[] f : flights) {
                int u = f[0], v = f[1], w = f[2];
                if (dp[i - 1][u] + w < dp[i][v]) {
                    dp[i][v] = dp[i - 1][u] + w;
                }
            }
        }
        return dp[K + 1][dst] == INF ? -1 : dp[K + 1][dst];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int n = 3;
        int[][] flights = {{0,1,100},{1,2,100},{0,2,500}};
        int src = 0, dst = 2, K = 1;
        System.out.println(sol.findCheapestPrice(n, flights, src, dst, K)); // 200
    }
}

Line Notes

int INF = Integer.MAX_VALUE / 2;Use large number to avoid overflow

int[][] dp = new int[K + 2][n];DP table for flights count and cities

Arrays.fill(dp[i], INF);Initialize costs to infinity

dp[i] = dp[i - 1].clone();Copy previous row to avoid overwriting

if (dp[i - 1][u] + w < dp[i][v])Relax edge if cheaper cost found

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        int INF = INT_MAX / 2;
        vector<vector<int>> dp(K + 2, vector<int>(n, INF));
        dp[0][src] = 0;
        for (int i = 1; i <= K + 1; i++) {
            dp[i] = dp[i - 1];
            for (auto &f : flights) {
                int u = f[0], v = f[1], w = f[2];
                if (dp[i - 1][u] + w < dp[i][v]) {
                    dp[i][v] = dp[i - 1][u] + w;
                }
            }
        }
        return dp[K + 1][dst] == INF ? -1 : dp[K + 1][dst];
    }
};

int main() {
    Solution sol;
    vector<vector<int>> flights = {{0,1,100},{1,2,100},{0,2,500}};
    cout << sol.findCheapestPrice(3, flights, 0, 2, 1) << endl; // 200
    return 0;
}

Line Notes

int INF = INT_MAX / 2;Large number to prevent overflow

vector<vector<int>> dp(K + 2, vector<int>(n, INF));DP table initialization

dp[0][src] = 0;Cost zero to reach source with zero flights

dp[i] = dp[i - 1];Copy previous costs to current row

if (dp[i - 1][u] + w < dp[i][v])Relax edge if cheaper cost found

function findCheapestPrice(n, flights, src, dst, K) {
    const INF = Number.MAX_SAFE_INTEGER;
    const dp = Array.from({length: K + 2}, () => Array(n).fill(INF));
    dp[0][src] = 0;
    for (let i = 1; i <= K + 1; i++) {
        dp[i] = dp[i - 1].slice();
        for (const [u, v, w] of flights) {
            if (dp[i - 1][u] !== INF && dp[i - 1][u] + w < dp[i][v]) {
                dp[i][v] = dp[i - 1][u] + w;
            }
        }
    }
    return dp[K + 1][dst] === INF ? -1 : dp[K + 1][dst];
}

// Example usage
console.log(findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1)); // 200

Line Notes

const dp = Array.from({length: K + 2}, () => Array(n).fill(INF));Initialize DP table with infinity

dp[0][src] = 0;Cost zero to reach source with zero flights

dp[i] = dp[i - 1].slice();Copy previous row to avoid overwriting

for (const [u, v, w] of flights)Relax edges for current flights count

dp[i][v] = dp[i - 1][u] + w;Update minimum cost if cheaper

⏱

Complexity

TimeO(K * E)

SpaceO(n * K)

For each of K+1 iterations, we relax all edges E once.

💡 If K=1 and E=3, we do about 2*3=6 relaxations, very efficient.

Interview Verdict: Accepted

This is the preferred approach for this problem in interviews due to clarity and efficiency.

🧠

Space Optimized Bottom-Up DP

💡 We can optimize space by using only two 1D arrays instead of a 2D DP table, since dp[i] depends only on dp[i-1].

Intuition

Keep track of costs for the previous iteration and update a new array for the current iteration, swapping them each time.

Algorithm

1. Initialize two arrays prev and curr with infinity, set prev[src] = 0.
2. For each iteration from 1 to K+1, copy prev to curr.
3. Relax all edges using prev to update curr.
4. Swap prev and curr for next iteration.
5. Return prev[dst] or -1 if unreachable.

💡 By swapping arrays, we avoid overwriting data needed for the current iteration, ensuring correctness with less memory.

Recurrence:curr[v] = min(curr[v], prev[u] + cost(u,v))

</>

Code

def findCheapestPrice(n, flights, src, dst, K):
    INF = float('inf')
    prev = [INF] * n
    prev[src] = 0
    for _ in range(K + 1):
        curr = prev[:]
        for u, v, w in flights:
            if prev[u] != INF:
                curr[v] = min(curr[v], prev[u] + w)
        prev = curr
    return prev[dst] if prev[dst] != INF else -1

# Example usage
if __name__ == '__main__':
    n = 3
    flights = [[0,1,100],[1,2,100],[0,2,500]]
    src = 0
    dst = 2
    K = 1
    print(findCheapestPrice(n, flights, src, dst, K))  # Output: 200

Line Notes

prev = [INF] * nInitialize previous iteration costs

prev[src] = 0Cost zero to reach source

curr = prev[:]Copy previous costs to current iteration

for u, v, w in flightsRelax edges using previous costs

curr[v] = min(curr[v], prev[u] + w)Update minimum cost for city v

prev = currPrepare for next iteration

import java.util.*;

public class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        int INF = Integer.MAX_VALUE / 2;
        int[] prev = new int[n];
        Arrays.fill(prev, INF);
        prev[src] = 0;
        for (int i = 0; i <= K; i++) {
            int[] curr = prev.clone();
            for (int[] f : flights) {
                int u = f[0], v = f[1], w = f[2];
                if (prev[u] + w < curr[v]) {
                    curr[v] = prev[u] + w;
                }
            }
            prev = curr;
        }
        return prev[dst] == INF ? -1 : prev[dst];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int n = 3;
        int[][] flights = {{0,1,100},{1,2,100},{0,2,500}};
        int src = 0, dst = 2, K = 1;
        System.out.println(sol.findCheapestPrice(n, flights, src, dst, K)); // 200
    }
}

Line Notes

int[] prev = new int[n];Array for previous iteration costs

Arrays.fill(prev, INF);Initialize with infinity

prev[src] = 0;Cost zero to reach source

int[] curr = prev.clone();Copy previous costs for current iteration

if (prev[u] + w < curr[v])Relax edge if cheaper cost found

prev = curr;Update prev for next iteration

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        int INF = INT_MAX / 2;
        vector<int> prev(n, INF);
        prev[src] = 0;
        for (int i = 0; i <= K; i++) {
            vector<int> curr = prev;
            for (auto &f : flights) {
                int u = f[0], v = f[1], w = f[2];
                if (prev[u] + w < curr[v]) {
                    curr[v] = prev[u] + w;
                }
            }
            prev = curr;
        }
        return prev[dst] == INF ? -1 : prev[dst];
    }
};

int main() {
    Solution sol;
    vector<vector<int>> flights = {{0,1,100},{1,2,100},{0,2,500}};
    cout << sol.findCheapestPrice(3, flights, 0, 2, 1) << endl; // 200
    return 0;
}

Line Notes

vector<int> prev(n, INF);Previous iteration costs

prev[src] = 0;Cost zero to reach source

vector<int> curr = prev;Copy previous costs for current iteration

if (prev[u] + w < curr[v])Relax edge if cheaper cost found

prev = curr;Update prev for next iteration

function findCheapestPrice(n, flights, src, dst, K) {
    const INF = Number.MAX_SAFE_INTEGER;
    let prev = new Array(n).fill(INF);
    prev[src] = 0;
    for (let i = 0; i <= K; i++) {
        let curr = prev.slice();
        for (const [u, v, w] of flights) {
            if (prev[u] !== INF && prev[u] + w < curr[v]) {
                curr[v] = prev[u] + w;
            }
        }
        prev = curr;
    }
    return prev[dst] === INF ? -1 : prev[dst];
}

// Example usage
console.log(findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1)); // 200

Line Notes

let prev = new Array(n).fill(INF);Previous iteration costs

prev[src] = 0;Cost zero to reach source

let curr = prev.slice();Copy previous costs for current iteration

if (prev[u] !== INF && prev[u] + w < curr[v])Relax edge if cheaper cost found

prev = curr;Update prev for next iteration

⏱

Complexity

TimeO(K * E)

SpaceO(n)

We only keep two arrays of size n, iterating K+1 times over all edges.

💡 For K=1 and E=3, this means 6 relaxations and only 2 arrays of size 3, very memory efficient.

Interview Verdict: Accepted

This is the most space-efficient approach and preferred when memory is constrained.

📊

All Approaches - One-Glance Tradeoffs

💡 Bottom-up DP with space optimization is best for interviews; memoization is good for understanding; brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^(K+1))	O(n) recursion stack	Yes (deep recursion)	No	Mention only - never code
2. Top-Down DP with Memoization	O(n * K * E)	O(n * K) memo	Possible but less than brute force	Yes with parent tracking	Good for explaining DP concepts
3. Bottom-Up DP (Bellman-Ford Variant)	O(K * E)	O(n * K)	No	Yes with parent tracking	Preferred approach to code
4. Space Optimized Bottom-Up DP	O(K * E)	O(n)	No	No (without extra tracking)	Mention as optimization if asked

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when to present each during interviews.

How to Present

Clarify problem constraints and inputs.Explain brute force DFS and its limitations.Introduce memoization to optimize recursion.Present bottom-up DP as the optimal iterative solution.Mention space optimization if memory is a concern.

Time Allocation

Clarify: 3min → Brute Force: 5min → Memoization: 7min → Bottom-Up DP: 7min → Testing & Follow-ups: 8min. Total ~30min

What the Interviewer Tests

Understanding of DP states and transitions, ability to optimize naive solutions, and knowledge of graph shortest path variants.

Common Follow-ups

• What if we want the actual path, not just cost? → Use parent pointers to reconstruct path.
• Can we use Dijkstra here? → Not directly due to stop constraints; Bellman-Ford variant is better.

💡 These follow-ups test deeper understanding of shortest path algorithms and path reconstruction.

🔍

Pattern Recognition

When to Use

1) Graph shortest path with constraints on stops or edges 2) Need to find minimum cost with limited steps 3) Overlapping subproblems with optimal substructure 4) Bellman-Ford or DP style relaxation fits

Signature Phrases

at most K stopscheapest priceflights between cities

NOT This Pattern When

Classic Dijkstra shortest path without constraints is a different pattern.

Similar Problems

Network Delay Time - similar shortest path with delaysMinimum Cost Path in Grid - DP with limited moves

Practice

1. Consider the following Python code implementing Kahn's Algorithm for course scheduling. What is the return value of canFinish(3, [[1,0],[2,1]]) after the while loop completes?

easy

A. false

B. true

C. Raises an error due to empty queue

D. Returns true only if numCourses is 2

Solution

1. Step 1: Initialize graph and in-degree arrays

   Graph: 0 -> [1], 1 -> [2], 2 -> []. In-degree: [0,1,1]. Queue starts with nodes having in-degree 0 -> [0].

2. Step 2: Process queue and update count

   Pop 0, count=1; decrement in-degree of 1 to 0, enqueue 1. Pop 1, count=2; decrement in-degree of 2 to 0, enqueue 2. Pop 2, count=3; queue empty.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   All courses processed, so return true [OK]

Hint: Count equals numCourses means no cycle [OK]

Common Mistakes:

• Off-by-one error in count increment
• Misunderstanding queue initialization
• Confusing in-degree decrement timing

2. Consider the following Python code implementing flood fill using DFS. Given the input image = [[1,1,1],[1,1,0],[1,0,1]], starting pixel (sr=1, sc=1), and newColor=2, what is the final image returned?

easy

A. [[1,1,1],[1,2,0],[1,0,1]]

B. [[2,2,2],[2,2,0],[2,0,2]]

C. [[2,2,2],[2,2,0],[2,0,1]]

D. [[2,2,2],[2,2,2],[2,2,2]]

Solution

1. Step 1: Trace dfs starting at (1,1) with original color=1

   The pixel at (1,1) is recolored to 2. Its neighbors with color 1 are (0,1), (2,1) is 0 so skipped, (1,0), and (1,2) is 0 skipped.

2. Step 2: Recursively recolor connected pixels with color 1

   All connected pixels with color 1 reachable from (1,1) are recolored to 2, resulting in [[2,2,2],[2,2,0],[2,0,1]]. The pixel at (2,2) remains 1 as it is not connected 4-directionally.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only connected pixels with original color changed [OK]

Hint: Trace DFS calls carefully to find connected pixels [OK]

Common Mistakes:

• Changing pixels diagonally connected
• Forgetting to check boundaries

3. Consider the following code snippet for the Keys and Rooms problem:

def canVisitAllRooms(rooms):
    n = len(rooms)
    visited = [false] * n
    count = 0
    def dfs(room):
        nonlocal count
        if visited[room]:
            return
        visited[room] = true
        count += 1
        if count == n:
            return
        for key in rooms[room]:
            dfs(key)
    dfs(0)
    return count == n

rooms = [[1], [2], [3], []]
print(canVisitAllRooms(rooms))

What is the value of count after the DFS call completes?

easy

A. 3

B. 0

C. 1

D. 4

Solution

1. Step 1: Trace DFS calls starting from room 0

   Visit room 0 (count=1), then room 1 (count=2), then room 2 (count=3), then room 3 (count=4).

2. Step 2: Confirm all rooms visited

   Since count equals total rooms (4), DFS stops early and returns true.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All rooms reachable, count matches number of rooms [OK]

Hint: Count increments once per unique room visited [OK]

Common Mistakes:

• Off-by-one error counting rooms
• Assuming count stops at 3 instead of 4
• Confusing count with length of visited list

4. Consider the following Python code implementing the Number of Islands problem using in-place DFS. Given the input grid below, what is the final returned value of numIslands(grid)?

grid = [
  ["1","1","0"],
  ["0","1","0"],
  ["1","0","1"]
]

easy

A. 1

B. 2

C. 4

D. 3

Solution

1. Step 1: Trace DFS calls starting from (0,0)

   DFS marks (0,0), (0,1), and (1,1) as visited, sinking one island.

2. Step 2: Identify remaining islands

   Next unvisited '1' is at (2,0) (second island), then at (2,2) (third island). Total islands counted = 3.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Counting connected components by DFS yields 3 islands [OK]

Hint: Count connected components by DFS marking visited [OK]

Common Mistakes:

• Off-by-one counting islands
• Missing diagonal connections (which don't count)

5. Consider the following code snippet implementing the optimal BFS approach for the Surrounded Regions problem. Given the input board:

board = [
  ['X', 'X', 'X', 'X'],
  ['X', 'O', 'O', 'X'],
  ['X', 'X', 'O', 'X'],
  ['X', 'O', 'X', 'X']
]

After the BFS marking completes, what is the value of board[3][1]?

easy

A. 'O'

B. 'X'

C. 'S'

D. IndexError (out of bounds)

Solution

1. Step 1: Identify boundary 'O's and mark them

   Only board[3][1] is a boundary 'O', so it is marked 'S' and added to the queue.

2. Step 2: BFS expands from (3,1) marking connected 'O's

   From (3,1), no adjacent 'O's inside the board are connected, so only (3,1) remains 'S'. After BFS, all 'S' revert to 'O'.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Boundary 'O' at (3,1) remains 'O' after processing [OK]

Hint: Boundary 'O's remain 'O' after BFS marking [OK]

Common Mistakes:

• Confusing 'S' with final 'O' or 'X' states.
• Forgetting to revert 'S' back to 'O' after BFS.
• Assuming all 'O's get flipped regardless of boundary connection.