Cheapest Flights Within K Stops

📋

Cheapest Flights Within K Stops

Edge cases:

</>

IDE

def findCheapestPrice(n: int, flights: list[list[int]], src: int, dst: int, K: int) -> int:public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K)int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K)function findCheapestPrice(n, flights, src, dst, K)

def findCheapestPrice(n, flights, src, dst, K):
    # Write your solution here
    pass

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        // Write your solution here
        return -1;
    }
}

#include <vector>
using namespace std;

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
    // Write your solution here
    return -1;
}

function findCheapestPrice(n, flights, src, dst, K) {
    // Write your solution here
    return -1;
}

Common Bugs to Avoid

Wrong: -1 when direct flight exists and K=0Not checking direct flights when K=0, returning -1 by default.✅ Add explicit check for direct flight from src to dst when K=0 and return its cost.

Wrong: Cost ignoring stops limit (e.g., 300 instead of 500)Greedy approach picking cheapest edges without enforcing stops limit.✅ Implement DP or BFS that tracks stops and only updates costs if stops ≤ K+1.

Wrong: Infinite loop or stack overflowDFS without pruning or memoization causing cycles and infinite recursion.✅ Limit recursion depth by stops and memoize visited states or use iterative DP.

Wrong: Wrong cost due to off-by-one stops countingMiscounting stops as nodes instead of edges or vice versa.✅ Define stops as edges and allow up to K+1 edges in path.

Wrong: TLE on large inputsUsing exponential DFS instead of DP with O(K*E) complexity.✅ Implement Bellman-Ford variant DP with K+1 iterations over edges.

✓

Test Cases

Focus on handling empty inputs and trivial cases like src == dst.

Test your solution against tricky cases with cycles and greedy traps.

Optimize your solution to run in O(K*E) time to handle large inputs.

t1_01basic

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

Expected200

⏱ Performance - must finish in 2000ms

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

💡 Think about using dynamic programming or shortest path algorithms with a stops limit.

💡 Consider a Bellman-Ford variant that relaxes edges up to K+1 times.

💡 Use a DP array where dp[i][j] is the cheapest cost to reach city j using at most i stops.

Why it failed: Failed basic canonical case: likely ignoring the stops limit or not updating costs correctly. Fix by implementing DP with stops constraint and proper edge relaxation.

✓ Correctly handles the canonical example with stops limit and cost calculation.

t1_02basic

Input{"n":4,"flights":[[0,1,50],[1,2,50],[2,3,50],[0,3,200]],"src":0,"dst":3,"K":2}

Expected150

⏱ Performance - must finish in 2000ms

Cheapest route 0->1->2->3 with cost 50+50+50=150 is cheaper than direct 0->3 flight costing 200, within 2 stops.

💡 Check all paths with up to K stops, not just direct flights.

💡 Use DP or BFS with a queue tracking stops and cost.

💡 Relax edges up to K+1 times to find minimum cost within stops limit.

Why it failed: Incorrect output due to ignoring multi-stop paths or not limiting stops properly. Fix by tracking stops and updating costs only if stops <= K+1.

✓ Correctly finds cheaper multi-stop route within stops limit.

t2_01edge

Input{"n":3,"flights":[],"src":0,"dst":2,"K":1}

Expected-1

⏱ Performance - must finish in 2000ms

No flights available, so no route exists; output is -1.

💡 Check if flights list is empty and handle no-route case.

💡 Return -1 if no path found after processing.

💡 Ensure base case returns -1 when no edges exist.

Why it failed: Returns incorrect cost instead of -1 when no flights exist. Fix by returning -1 if no path found after DP or BFS.

✓ Correctly returns -1 when no flights are available.

t2_02edge

Input{"n":1,"flights":[],"src":0,"dst":0,"K":0}

Expected0

⏱ Performance - must finish in 2000ms

Source equals destination, cost is zero regardless of flights or stops.

💡 Check if src equals dst and return 0 immediately.

💡 This is a base case with no travel needed.

💡 Add a condition to handle src == dst before DP or BFS.

Why it failed: Fails to return 0 when src == dst, returning -1 or wrong cost. Fix by adding early return for src == dst.

✓ Correctly returns 0 when source equals destination.

t2_03edge

Input{"n":3,"flights":[[0,2,300]],"src":0,"dst":2,"K":0}

Expected300

⏱ Performance - must finish in 2000ms

K=0 allows only direct flights; direct flight 0->2 costs 300.

💡 When K=0, only direct flights are allowed.

💡 Check for direct edge from src to dst.

💡 Return direct flight cost if exists, else -1.

Why it failed: Fails to handle K=0 direct flight case, returning -1 or wrong cost. Fix by checking direct flights when K=0.

✓ Correctly returns direct flight cost when K=0.

t2_04edge

Input{"n":2,"flights":[[0,1,100]],"src":0,"dst":1,"K":0}

Expected100

⏱ Performance - must finish in 2000ms

Minimal input with direct flight and zero stops allowed returns direct flight cost.

💡 Test minimal input with direct flight and K=0.

💡 Ensure direct flight cost is returned correctly.

💡 Check stops limit and direct edge existence.

Why it failed: Fails to return direct flight cost for minimal input with K=0. Fix by handling direct flights properly.

✓ Correctly returns direct flight cost for minimal input.

t3_01corner

Input{"n":4,"flights":[[0,1,100],[1,2,100],[2,3,100],[0,3,500]],"src":0,"dst":3,"K":1}

Expected500

⏱ Performance - must finish in 2000ms

Greedy approach picking cheapest edges first fails; best route with ≤1 stop is direct 0->3 costing 500, not 0->1->2->3 (3 stops).

💡 Beware of greedy approaches that pick cheapest edges without stop limit.

💡 Stops limit means paths with more than K stops are invalid.

💡 Use DP or BFS with stops count to enforce stop constraints.

Why it failed: Greedy approach returns 300 (0->1->2->3) ignoring stops limit. Fix by enforcing stops ≤ K+1 in DP or BFS.

✓ Correctly enforces stops limit and returns direct flight cost.

t3_02corner

Input{"n":3,"flights":[[0,1,100],[1,0,50],[1,2,100]],"src":0,"dst":2,"K":1}

Expected200

⏱ Performance - must finish in 2000ms

Confusing 0/1 vs unbounded stops: cycles exist but stops limit prevents infinite loops; cost is 0->1->2 = 200.

💡 Avoid infinite loops by limiting stops to K+1.

💡 Do not treat problem as unbounded knapsack; stops are limited.

💡 Use DP or BFS with stops count to prevent cycles beyond limit.

Why it failed: Fails by allowing cycles or infinite loops ignoring stops limit. Fix by tracking stops and pruning paths exceeding K+1 stops.

✓ Correctly handles stops limit and prevents infinite cycles.

t3_03corner

Input{"n":5,"flights":[[0,1,10],[1,2,10],[2,3,10],[3,4,10],[0,4,100]],"src":0,"dst":4,"K":3}

Expected40

⏱ Performance - must finish in 2000ms

Off-by-one error in stops counting: path 0->1->2->3->4 has 4 edges but 3 stops allowed means 4 edges max; cost 40 is valid.

💡 Clarify definition of stops: number of edges or intermediate nodes.

💡 Stops limit K means at most K+1 edges in path.

💡 Ensure DP or BFS counts stops correctly to include valid paths.

Why it failed: Off-by-one error causes rejecting valid path or accepting invalid path. Fix by defining stops as edges and allowing up to K+1 edges.

✓ Correctly counts stops and returns minimal cost.

t4_01performance

Input{"n":100,"flights":[[0,1,10],[1,2,10],[2,3,10],[3,4,10],[4,5,10],[5,6,10],[6,7,10],[7,8,10],[8,9,10],[9,10,10],[10,11,10],[11,12,10],[12,13,10],[13,14,10],[14,15,10],[15,16,10],[16,17,10],[17,18,10],[18,19,10],[19,20,10],[20,21,10],[21,22,10],[22,23,10],[23,24,10],[24,25,10],[25,26,10],[26,27,10],[27,28,10],[28,29,10],[29,30,10],[30,31,10],[31,32,10],[32,33,10],[33,34,10],[34,35,10],[35,36,10],[36,37,10],[37,38,10],[38,39,10],[39,40,10],[40,41,10],[41,42,10],[42,43,10],[43,44,10],[44,45,10],[45,46,10],[46,47,10],[47,48,10],[48,49,10],[49,50,10],[50,51,10],[51,52,10],[52,53,10],[53,54,10],[54,55,10],[55,56,10],[56,57,10],[57,58,10],[58,59,10],[59,60,10],[60,61,10],[61,62,10],[62,63,10],[63,64,10],[64,65,10],[65,66,10],[66,67,10],[67,68,10],[68,69,10],[69,70,10],[70,71,10],[71,72,10],[72,73,10],[73,74,10],[74,75,10],[75,76,10],[76,77,10],[77,78,10],[78,79,10],[79,80,10],[80,81,10],[81,82,10],[82,83,10],[83,84,10],[84,85,10],[85,86,10],[86,87,10],[87,88,10],[88,89,10],[89,90,10],[90,91,10],[91,92,10],[92,93,10],[93,94,10],[94,95,10],[95,96,10],[96,97,10],[97,98,10],[98,99,10],[0,99,1000]],"src":0,"dst":99,"K":50}

Expected-1

⏱ Performance - must finish in 2000ms

n=100, flights=100 edges, K=50; O(K*E) DP must complete within 2s.

💡 Use Bellman-Ford variant with K+1 iterations over edges.

💡 Avoid DFS exponential time; use DP or BFS with stops limit.

💡 Optimize space by storing only current and previous iteration costs.

Why it failed: TLE due to exponential DFS or naive recursion. Fix by implementing DP with O(K*E) complexity.

✓ Efficient DP solution runs within time limit.

Practice

1. Consider the following Python function implementing the minimum falling path sum using bottom-up DP:

def minFallingPathSum(matrix):
    n = len(matrix)
    dp = matrix[0][:]

    for i in range(1, n):
        new_dp = [0]*n
        for j in range(n):
            best = dp[j]
            if j > 0:
                best = min(best, dp[j-1])
            if j < n - 1:
                best = min(best, dp[j+1])
            new_dp[j] = matrix[i][j] + best
        dp = new_dp

    return min(dp)

matrix = [[2,1,3],[6,5,4],[7,8,9]]
print(minFallingPathSum(matrix))

What is the output of this code?

easy

A. 12

B. 13

C. 14

D. 15

Solution

1. Step 1: Trace dp after first row

   dp = [2, 1, 3]

2. Step 2: Compute dp for second row

   For i=1: - j=0: best = min(dp[0], dp[1]) = min(2,1) = 1 -> new_dp[0] = 6 + 1 = 7 - j=1: best = min(dp[1], dp[0], dp[2]) = min(1,2,3) = 1 -> new_dp[1] = 5 + 1 = 6 - j=2: best = min(dp[2], dp[1]) = min(3,1) = 1 -> new_dp[2] = 4 + 1 = 5 So new_dp = [7, 6, 5]

3. Step 3: Compute dp for third row

   For i=2: - j=0: best = min(new_dp[0], new_dp[1]) = min(7,6) = 6 -> new_dp[0] = 7 + 6 = 13 - j=1: best = min(new_dp[1], new_dp[0], new_dp[2]) = min(6,7,5) = 5 -> new_dp[1] = 8 + 5 = 13 - j=2: best = min(new_dp[2], new_dp[1]) = min(5,6) = 5 -> new_dp[2] = 9 + 5 = 14 So new_dp = [13, 13, 14]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Minimum of last dp row is 13 [OK]

Hint: Trace dp row by row, pick min at end [OK]

Common Mistakes:

• Off-by-one in indices
• Using old dp instead of new_dp values

2. 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

3. What is the time and space complexity of the space-optimized bottom-up dynamic programming solution for the Minimum Path Sum problem on an m x n grid?

medium

A. Time: O(m*n), Space: O(m*n)

B. Time: O(m*n), Space: O(m)

C. Time: O(2^(m+n)), Space: O(m+n)

D. Time: O(m*n), Space: O(n)

Solution

1. Step 1: Identify time complexity

   The algorithm iterates over each cell once, so time is O(m*n).

2. Step 2: Identify space complexity

   Space optimized DP uses a single 1D array of length n, so space is O(n), not O(m*n) or O(m).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single dp array of size n updated row by row [OK]

Hint: Space optimized DP uses one row array, not full matrix [OK]

Common Mistakes:

• Assuming space is O(m*n) due to 2D dp
• Confusing recursion stack space with DP space
• Mistaking m for n in space complexity

4. Identify the bug in the following code snippet for minimum score triangulation of a polygon:

medium

A. Line missing dp[i][j] = float('inf') before minimization

B. Line initializing dp array with zeros

C. Loop boundaries for k from i+1 to j-1

D. Return statement returning dp[0][n-1]

Solution

1. Step 1: Check dp initialization inside loops

   dp[i][j] must be set to infinity before checking for minimal cost; otherwise, dp[i][j] starts at 0 and may never update correctly.

2. Step 2: Confirm other lines are correct

   dp array initialization, loop boundaries, and return statement are correct and standard.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without dp[i][j] = float('inf'), minimal cost calculation is incorrect [OK]

Hint: Always initialize dp[i][j] before minimization [OK]

Common Mistakes:

• Forgetting dp initialization
• Off-by-one in loops
• Mixing indices i,j,k

5. Consider the following buggy code for Paint House (K Colors). Which line contains the subtle bug that can cause adjacent houses to have the same color, violating constraints?

medium

A. Line with 'min_prev = min(dp[x] for x in range(k))'

B. Line with 'dp = costs[0][:]' initialization

C. Line with 'new_dp = [0]*k' inside the loop

D. Line with 'return min(dp)' at the end

Solution

1. Step 1: Identify constraint violation

   The problem requires that adjacent houses cannot have the same color. The code must exclude the current color when computing min_prev.

2. Step 2: Locate bug in min_prev calculation

   The line 'min_prev = min(dp[x] for x in range(k))' includes the current color's dp value, allowing same color adjacency, violating constraints.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Excluding current color in min calculation is essential [OK]

Hint: Check if min excludes current color to avoid same-color adjacency [OK]

Common Mistakes:

• Including current color in min calculation
• Incorrect dp initialization
• Returning min(dp) without proper updates