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. You need to paint n houses, each with one of k colors. Adjacent houses cannot share the same color. Each color choice has a cost per house. Which algorithmic approach guarantees finding the minimum total painting cost efficiently?

easy

A. Dynamic Programming that tracks minimum costs per house and color, avoiding same-color adjacency

B. Depth-first search exploring all color combinations without memoization

C. Greedy algorithm choosing the cheapest color for each house independently

D. Sorting houses by cost and assigning colors in ascending order

Solution

1. Step 1: Understand problem constraints

   The problem requires minimizing total cost with the constraint that no two adjacent houses share the same color.

2. Step 2: Identify suitable algorithm

   Greedy fails because local cheapest choice may cause conflicts later. DFS without memoization is exponential. Sorting houses by cost ignores adjacency constraints. DP tracks costs per house and color, ensuring constraints and optimal substructure.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP explicitly handles adjacency and cost minimization [OK]

Hint: DP tracks costs per house and color with adjacency constraints [OK]

Common Mistakes:

• Assuming greedy choice is globally optimal
• Ignoring adjacency constraints in sorting
• Not using memoization in recursion

2. Consider the following bottom-up DP code for the Triangle minimum path sum problem. Given the input triangle = [[2],[3,4],[6,5,7]], what is the value of dp after the first iteration of the outer loop (i = 1)?

easy

A. [8, 9, 7]

B. [9, 10, 7]

C. [11, 10, 7]

D. [7, 9, 7]

Solution

1. Step 1: Initialize dp with last row

   dp = [6, 5, 7]

2. Step 2: Compute dp for i=1 (row [3,4])

   For j=0: dp[0] = 3 + min(6,5) = 3 + 5 = 8 For j=1: dp[1] = 4 + min(5,7) = 4 + 5 = 9 Updated dp = [8, 9, 7]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp updated correctly for row 1 [OK]

Hint: dp[j] updated using min of dp[j], dp[j+1] from row below [OK]

Common Mistakes:

• Off-by-one error in indexing dp
• Not copying last row correctly
• Mixing up dp[j] and dp[j+1] in min calculation

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

4. What is the time complexity of the bottom-up DP solution for the Strange Printer problem after string compression, where m is the length of the compressed string?

medium

A. O(m^2)

B. O(m^3)

C. O(n^3) where n is original string length

D. O(m^2 * log m)

Solution

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

   There are three nested loops: length (1 to m), start index i (up to m), and partition index k (between i and j), each up to m.

2. Step 2: Calculate complexity

   Overall complexity is O(m * m * m) = O(m^3). Compression reduces n to m, so complexity depends on compressed length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Three nested loops over compressed length m [OK]

Hint: Three nested loops over compressed string length cause cubic time [OK]

Common Mistakes:

• Confusing original length n with compressed length m
• Forgetting the inner loop over k

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