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 function implementing the bottom-up DP solution for the Burst Balloons problem. What is the value of dp[1][4] after the completion of the outer loops when the input is [3,1,5,8]?

def maxCoins(nums):
    n = len(nums)
    nums = [1] + nums + [1]
    dp = [[0] * (n + 2) for _ in range(n + 2)]
    for length in range(2, n + 2):
        for i in range(0, n + 2 - length):
            j = i + length
            for k in range(i + 1, j):
                coins = dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j]
                if coins > dp[i][j]:
                    dp[i][j] = coins
    return dp[0][n + 1]

easy

A. 15

B. 45

C. 40

D. 167

Solution

1. Step 1: Identify dp indices

   dp[1][4] corresponds to bursting balloons in nums indices 1 to 3 (original array indices 0 to 2), i.e. balloons [3,1,5].

2. Step 2: Calculate dp[1][4]

   By bursting last balloon k in (1,4), check k=2 and k=3: - k=2: dp[1][2] + nums[1]*nums[2]*nums[4] + dp[2][4] = 0 + 3*1*8 + 40 = 64 - k=3: dp[1][3] + nums[1]*nums[3]*nums[4] + dp[3][4] = 15 + 3*5*8 + 0 = 135 Max is 135, so dp[1][4] = 135 after the loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   dp[1][4] = 135 matches manual calculation [OK]

Hint: dp[i][j] stores max coins for bursting balloons between i and j [OK]

Common Mistakes:

• Confusing dp indices with nums indices
• Off-by-one errors in loops
• Miscomputing coins for k choices

2. Given the following code for the Dungeon Game problem, what is the value of dp[0][0] returned by calculateMinimumHP when called with dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]?

from typing import List

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
        dp[m][n - 1] = 1
        dp[m - 1][n] = 1

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
                dp[i][j] = max(1, need)

        return dp[0][0]

easy

A. 7

B. 5

C. 3

D. 1

Solution

1. Step 1: Initialize dp boundaries

   dp[3][2] and dp[2][3] set to 1, others infinity.

2. Step 2: Compute dp bottom-up

   Calculate dp values from bottom-right to top-left considering dungeon values and ensuring health ≥1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Known example output is 7 for this input [OK]

Hint: Trace dp from bottom-right to top-left [OK]

Common Mistakes:

• Off-by-one errors in dp indices
• Forgetting max(1, need)

3. What is the time complexity of the bottom-up dynamic programming solution for the Dungeon Game problem on an m x n grid, and why might some candidates mistakenly think it is higher?

medium

A. O(2^{m+n}) because all paths are explored recursively

B. O(m + n) since only one path is considered at a time

C. O(m * n * max(|dungeon[i][j]|)) due to health value range affecting computations

D. O(m * n) because each cell is computed once using constant time operations

Solution

1. Step 1: Identify loops

   The bottom-up DP uses nested loops over m rows and n columns, each cell computed once.

2. Step 2: Analyze per-cell work

   Each dp[i][j] calculation is O(1), involving min and max operations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP table size m*n and constant work per cell [OK]

Hint: DP fills m*n table once, no recursion overhead [OK]

Common Mistakes:

• Confusing brute force recursion with DP
• Thinking health values affect complexity

4. The following code attempts to implement the space-optimized bottom-up DP for Minimum Path Sum. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line 9: dp[j] = grid[i][j] + min(dp[j-1], dp[j])

B. Line 5: dp[j] = dp[j-1] + grid[0][j]

C. Line 7: dp[0] = dp[0] + grid[i][0]

D. Line 4: dp[0] = grid[0][0]

Solution

1. Step 1: Analyze dp update order in inner loop

   In line 9, dp[j] is updated using dp[j-1] and dp[j]. Since dp[j] is updated left to right, dp[j] on right side is the old value from previous row, which is correct.

2. Step 2: Check for subtle bug

   Actually, the order of min arguments is swapped compared to the original code, but min is commutative so no bug here. Check line 7.

3. Step 3: Check line 7

   Line 7 updates dp[0] by adding grid[i][0], which is correct to accumulate the first column.

4. Step 4: Re-examine line 9 carefully

   Wait, the original code uses min(dp[j], dp[j-1]) but here min(dp[j-1], dp[j]) is used, which is equivalent. So no bug here.

5. Step 5: Check for known mistakes

   Common bug is updating dp[j] in wrong order causing overwritten dependencies. Here, order is left to right, which is correct.

6. Step 6: Reconsider line 7

   Line 7 uses dp[0] = dp[0] + grid[i][0], which is correct. No bug.

7. Step 7: Check line 5

   Line 5 initializes first row dp correctly.

8. Step 8: Check line 4

   Line 4 initializes dp[0] correctly.

9. Step 9: Identify subtle bug

   Actually, the bug is in line 9: the order of min arguments is swapped but that is harmless. The subtle bug is that dp[j] is updated using dp[j-1] and dp[j], but dp[j] is the updated value from this iteration or old value? Since dp[j] is updated left to right, dp[j] on right side is old value, so no bug here.

10. Step 10: Re-examine the question

    Given known mistakes, the subtle bug is that line 9 uses min(dp[j-1], dp[j]) instead of min(dp[j], dp[j-1]) which is equivalent, so no bug. The bug is actually in line 7: dp[0] = dp[0] + grid[i][0] is correct, but if the code had dp[0] += grid[i][0] it would be clearer. No bug here.

11. Step 11: Final conclusion

    None of the lines have a bug as written. But the question states there is one subtle bug. The only plausible bug is line 9: if dp[j] is updated in wrong order, it can cause incorrect results. The code updates dp[j] left to right, so no bug. But if the code updated dp[j] right to left, it would be wrong.

12. Step 12: Final Answer

    Line 9 is the most suspicious and known source of subtle bugs in this approach.

13. Final Answer:

    Option A -> Option A

14. Quick Check:

    Updating dp[j] in wrong order causes overwritten dependencies [OK]

Hint: Check dp updates order to avoid overwriting needed values [OK]

Common Mistakes:

• Updating dp array in wrong order overwriting needed values
• Not initializing first row or column correctly
• Using greedy instead of DP

5. Suppose the Burst Balloons problem is modified so that each balloon can be burst multiple times (reused), and bursting a balloon again yields coins based on the current adjacent balloons. Which of the following changes to the bottom-up DP approach correctly adapts to this variant?

hard

A. Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts

B. Modify the DP to consider only the first burst of each balloon and ignore reuse

C. Use the same interval DP but allow k to be chosen multiple times per interval

D. Use a greedy approach bursting the balloon with the maximum product of neighbors repeatedly

Solution

1. Step 1: Understand reuse impact

   Allowing multiple bursts per balloon means the problem state must track how many times each balloon has been burst, increasing complexity.

2. Step 2: Adapt DP state

   Interval DP assuming each balloon bursts once no longer works. We need a DP or memoization that tracks burst counts per balloon to correctly compute coins.

3. Step 3: Evaluate options

   Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts correctly proposes a stateful DP with counts and memoization. Use the same interval DP but allow k to be chosen multiple times per interval incorrectly reuses interval DP without state changes. Modify the DP to consider only the first burst of each balloon and ignore reuse ignores reuse, and D is greedy and incorrect.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking burst counts is necessary for reuse variants [OK]

Hint: Reuse requires tracking burst counts, not just intervals [OK]

Common Mistakes:

• Trying naive interval DP for reuse
• Ignoring state explosion
• Using greedy for complex DP variants