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 code implementing Kahn's Algorithm for course scheduling. What is the return value of canFinish(3, [[1,0],[2,1]]) after the while loop completes?

easy

A. false

B. true

C. Raises an error due to empty queue

D. Returns true only if numCourses is 2

Solution

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

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

2. Step 2: Process queue and update count

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

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   All courses processed, so return true [OK]

Hint: Count equals numCourses means no cycle [OK]

Common Mistakes:

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

2. Examine the following buggy code snippet for the optimal BFS approach. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line that sets dist[nr][nc] = dist[r][c] + 1 without checking if dist[nr][nc] == -1

B. Line that initializes dist[r][c] = 0 for land cells

C. Line that appends initial land cells to the queue

D. Line that returns -1 if all cells are land or water

Solution

1. Step 1: Identify that updating dist[nr][nc] without checking if it was visited causes overwriting distances.

   This leads to revisiting cells multiple times, causing infinite loops or incorrect distances.

2. Step 2: The missing condition dist[nr][nc] == -1 before updating and enqueueing is the bug.

   Without it, BFS does not behave correctly as a shortest path search.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Visited check prevents infinite loops and ensures correct distances [OK]

Hint: Always check if neighbor is unvisited before updating distance [OK]

Common Mistakes:

• Forgetting visited check causes infinite loops
• Misplacing initialization lines
• Incorrect early return conditions

3. What is the time complexity of the optimal frequency counting approach to find the center of a star graph with n nodes and n-1 edges?

medium

A. O(n log n) due to sorting the frequency dictionary keys

B. O(n²) because each node's frequency is checked against all others

C. O(n) because each edge is processed once and frequency dictionary updates are O(1)

D. O(n + m) where m is the number of edges, which equals n-1 here

Solution

1. Step 1: Analyze edge processing

   Each of the n-1 edges is processed once, updating frequency counts in O(1) time per update.

2. Step 2: Frequency dictionary iteration

   Iterating over frequencies of up to n nodes is O(n), no sorting involved.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear time complexity matches single pass over edges and nodes [OK]

Hint: Frequency updates and iteration are O(1) and O(n) respectively [OK]

Common Mistakes:

• Assuming sorting is needed, adding O(n log n)
• Confusing number of edges with n² complexity
• Thinking frequency updates take O(n) each

4. Suppose the course prerequisites can include self-dependencies (a course requiring itself) and multiple edges between the same courses. Which modification to the Kahn's Algorithm is necessary to correctly detect cycles in this scenario?

hard

A. Ignore self-loops and treat multiple edges as one; no algorithm change needed.

B. Use DFS with coloring instead of Kahn's Algorithm because BFS cannot detect self-loops.

C. Modify in-degree initialization to count self-loops and multiple edges correctly.

D. Add a check to detect self-loops explicitly before running Kahn's Algorithm.

Solution

1. Step 1: Understand impact of self-loops and multiple edges

   Self-loops increase in-degree of a node, and multiple edges increase in-degree counts accordingly.

2. Step 2: Modify in-degree initialization to count all edges accurately

   Counting all edges including self-loops ensures Kahn's Algorithm correctly identifies cycles by never reducing in-degree to zero for cyclic nodes.

3. Step 3: Confirm no other algorithm change needed

   Algorithm logic remains the same; accurate in-degree counts handle these cases.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Proper in-degree counts detect cycles including self-loops [OK]

Hint: Count all edges correctly to detect cycles including self-loops [OK]

Common Mistakes:

• Ignoring self-loops leads to false positives
• Assuming BFS cannot detect self-loops
• Treating multiple edges as single edge incorrectly

5. Suppose the problem is modified so that you can revisit cells multiple times (cycles allowed) and want to find the minimum effort path. Which approach correctly adapts to this change?

hard

A. Use the same Dijkstra's variant without changes; revisiting is naturally handled

B. Use binary search over effort and BFS to check feasibility without distance updates

C. Use DFS with pruning to explore all paths allowing revisits

D. Modify Dijkstra to allow updating distances even if a node was visited before, to handle cycles

Solution

1. Step 1: Understand revisiting impact

   Allowing revisits means shortest path distances can improve after initial visit, so standard Dijkstra's visited set is insufficient.

2. Step 2: Adapt algorithm

   Dijkstra must allow updating distances and pushing nodes multiple times to handle cycles correctly.

3. Step 3: Evaluate other options

   DFS is inefficient; binary search + BFS may work but requires careful feasibility checks; naive Dijkstra fails.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Allowing distance updates handles cycles correctly [OK]

Hint: Cycles require relaxing visited constraints in Dijkstra [OK]

Common Mistakes:

• Assuming no changes needed for revisits
• Using DFS without pruning causes TLE
• Binary search feasibility fails without updates