Learning Outcome
Weighted shortest paths, constrained stops, probability paths, and grid costs.
Pattern Recognition
| Item | Detail |
|---|---|
| Core signal | A known interview family appears and the constraints reward the standard pattern. |
| Use when | Dijkstra is BFS with a priority queue when edges have non-uniform non-negative cost. |
| Avoid when | The required invariant is not monotonic or the input constraints point to a simpler direct scan. |
Intuition
Dijkstra is BFS with a priority queue when edges have non-uniform non-negative cost.
Exact Practice Question Names
- Network Delay Time
- Path with Maximum Probability
- Cheapest Flights Within K Stops
- Minimum Obstacle Removal to Reach Corner
- The Maze II
Interview Approach
- Name the exact family.
- Write the invariant or state.
- Pick the standard container or recurrence.
- Dry-run the smallest example.
- State complexity and one follow-up.
Pseudocode
identify pattern
initialize state/container
for each input unit:
update state safely
update answer when invariant is valid
return answerSample Dry Run
Take the smallest Dijkstra and Shortest Path example, track the state after every operation, and verify the final answer before coding.
Edge Cases
- Empty or single-item input
- Duplicate values
- Boundary constraints
- Large values requiring long/int64
Common Mistakes
- Memorizing code without naming the invariant
- Skipping the brute-force baseline
- Not explaining why the optimized approach is correct
Complexity
| Item | Detail |
|---|---|
| Expected time | Usually O(n log n), O(V + E), or states times transitions depending on the family. |
| Expected space | Usually O(n), O(V + E), or number of DP states. |
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.