Cheapest Flights Within K Stops - Video Solutions

Problem Overview: You are given n cities connected by flights where each edge has a price. The task is to find the cheapest cost from src to dst using at most k stops. The challenge is balancing shortest-path logic with a constraint on the number of intermediate nodes.

Approach 1: Breadth-First Search with Cost Tracking (Time: O(E * K), Space: O(V + E))

This approach treats the graph as levels of stops and explores it using Breadth-First Search. Build an adjacency list from the flights array, then perform BFS where each level represents one additional stop. Maintain the current cost to each node and only continue exploring if the new path is cheaper than previously recorded costs. The key insight is limiting traversal depth to k + 1 edges while pruning expensive paths early. This keeps exploration efficient even if the graph has many connections.

Approach 2: Dijkstra's Algorithm with Stop Constraint (Time: O(E log (V * K)), Space: O(V * K))

This method adapts shortest path logic using a min-heap (priority queue). Instead of storing only the node and cost, the state also tracks how many stops were used to reach the node. The heap always expands the cheapest path first. When a node is popped, its neighbors are pushed with updated cost and stop count, as long as the stop limit has not been exceeded. This guarantees the cheapest valid route is discovered early and works well when flight graphs are dense.

Recommended for interviews: Interviewers usually expect the Dijkstra-style solution because it directly models the constrained shortest-path problem and demonstrates familiarity with priority queues. Starting with the BFS idea shows you understand graph traversal with level constraints, but implementing the heap-based approach shows stronger mastery of graph optimization techniques.