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 code snippet for the Stone Game problem. What is the value of dp[0][3] after the completion of all loops when input piles = [5, 3, 4, 5]?

def stoneGame(piles):
    n = len(piles)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = piles[i]
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
    return dp[0][n-1] > 0

easy

A. 2

B. 0

C. 3

D. 1

Solution

1. Step 1: Initialize dp for single piles

   dp[i][i] = piles[i], so dp[0][0]=5, dp[1][1]=3, dp[2][2]=4, dp[3][3]=5.

2. Step 2: Compute dp for length=2 to 4

   For length=2, dp[0][1] = max(5 - 3, 3 - 5) = max(2, -2) = 2; similarly compute others. For length=4, dp[0][3] = max(5 - dp[1][3], 5 - dp[0][2]) = max(5 - 1, 5 - 4) = max(4, 1) = 4. But since dp stores difference, the final dp[0][3] = 1 after all calculations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual trace confirms dp[0][3] = 1 [OK]

Hint: Trace dp table diagonally from single piles [OK]

Common Mistakes:

• Off-by-one errors in indices
• Confusing dp values with total stones

2. What is the time complexity of the bottom-up dynamic programming solution for the Stone Game problem with n piles, and why?

medium

A. O(n^3) because of three nested loops over the piles

B. O(n^2) because the DP table of size nxn is filled once with constant work per cell

C. O(2^n) because all subsets of piles are considered

D. O(n) because only linear passes over the piles are needed

Solution

1. Step 1: Identify loops in bottom-up DP

   There are two nested loops: one for length from 2 to n, and one for start index i, total O(n^2) iterations.

2. Step 2: Constant work per dp[i][j]

   Each dp[i][j] is computed with a constant number of operations (max of two values), so total time is O(n^2).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP table size nxn filled once with O(1) work per cell [OK]

Hint: Two nested loops over intervals -> O(n^2) [OK]

Common Mistakes:

• Confusing recursion stack space with time
• Assuming triple nested loops cause O(n^3)

3. The following code attempts to compute the number of unique paths in an m x n grid using a space-optimized DP approach:

def uniquePaths(m, n):
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] = dp[j] + dp[j]
    return dp[-1]

What is the bug in this code?

medium

A. Line 3 should start loop from 0 instead of 1

B. Line 4 incorrectly doubles dp[j] instead of adding dp[j-1]

C. Line 5 should return dp[0] instead of dp[-1]

D. Line 2 initializes dp with wrong size

Solution

1. Step 1: Analyze inner loop update

   Line 4 updates dp[j] by adding dp[j] to itself, doubling the value instead of adding dp[j-1].

2. Step 2: Identify correct update

   The correct update is dp[j] += dp[j - 1] to accumulate paths from left and top cells.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Doubling dp[j] breaks path count logic -> bug at line 4 [OK]

Hint: Check dp update uses dp[j-1], not dp[j] twice [OK]

Common Mistakes:

• Using dp[j] + dp[j] instead of dp[j] + dp[j-1]
• Off-by-one errors in loops

4. What is the time complexity of the optimal interval DP solution for Zuma Game (Min Moves to Clear) with board length n and hand size m, considering the state space and transitions?

medium

A. O(n^4 * m^5)

B. O(n^2 * m^3)

C. O(n^3 * m^4)

D. O(5^(n+m))

Solution

1. Step 1: Identify DP state dimensions

   The DP state depends on intervals of the board (O(n^2)) and hand counts (up to 5 colors, each up to m), leading to O(n^3 * m^4) states due to interval splits and hand count combinations.

2. Step 2: Analyze transitions and recursion

   Each state considers splits and insertions, adding an extra factor of n and m, resulting in O(n^3 * m^4) time complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Complexity matches known analysis for interval DP with hand states [OK]

Hint: Interval splits and hand states multiply complexity [OK]

Common Mistakes:

• Confusing n^2 intervals with n^3 due to splits
• Ignoring hand state dimension leading to underestimation
• Mistaking brute force complexity for DP complexity

5. Suppose the triangle can contain negative numbers and you want to find the minimum path sum. Which modification to the bottom-up DP approach is necessary to correctly handle this variant?

hard

A. Add a check to reset dp values to zero if they become negative during updates

B. Use top-down DP with memoization to avoid incorrect overwrites caused by negative values

C. No modification needed; the existing bottom-up DP works for negative numbers as well

D. Use a breadth-first search to find the minimum path sum instead of DP

Solution

1. Step 1: Understand DP correctness with negative numbers

   Bottom-up DP computes minimum sums by combining current value with min of two below; negative values do not break this logic.

2. Step 2: Confirm no overwrite or invalid assumptions

   DP updates are independent of sign; no reset or BFS needed.

3. Step 3: Conclude no modification needed

   The existing bottom-up DP approach correctly handles negative numbers without changes.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   DP min operations handle negatives naturally [OK]

Hint: DP min works regardless of sign [OK]

Common Mistakes:

• Assuming negative numbers require resetting dp
• Thinking BFS is needed for negative weights
• Believing top-down memoization fixes negative value issues