Deep Dive: Cheapest Flights and K Stops

Learning Outcome

Build interview depth for Cheapest Flights and K Stops.

Pattern Recognition

Intuition

Stops add another state dimension, so plain Dijkstra distance per node is not enough.

Exact Practice Question Names

• Cheapest Flights Within K Stops

Interview Approach

1. Start with the base family.
2. Identify the new state or constraint.
3. Show why the simpler approach fails.
4. Add the smallest extra state needed.
5. Dry-run a follow-up example.

Pseudocode

base_pattern_state
extra_state_from_followup
process in valid order
relax/update answer
return final state
  

Sample Dry Run

Use one small Cheapest Flights and K Stops sample and explicitly track the extra state introduced by the follow-up.

Edge Cases

• Disconnected/unreachable state
• Cycles or repeated states
• Large constraints
• Tie-breaking

Common Mistakes

• Forcing the base template without adding required state
• Not proving why revisits are safe or unsafe
• Missing cycle handling

Complexity

Java, C++ and Python Notes

• Java: prefer explicit classes and clear helper methods over clever one-liners.
• C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
• Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.

Quick Revision Checklist

• Name the pattern before coding.
• State the invariant or DP state in one sentence.
• Dry-run the smallest non-trivial example.
• Close with time and space complexity.