What is the time and space complexity of Cheapest Flights Within K Stops?

Time complexity: O(K * E). Space complexity: O(V).

Cheapest Flights Within K Stops

Hard

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Cheapest Flights Within K Stops

Approach

Relax all edges exactly k+1 times, representing paths with up to k intermediate stops. Copy previous distances each round to avoid using newly updated values in same round.

Complexity Analysis

Time: O(K * E)
Space: O(V)

Pattern

DP by Edge Count (Bellman-Ford)

Why It Works

Any path with at most K stops has at most K+1 edges. Each iteration allows one extra edge, and relaxation accumulates best costs constrained by edge count.

Updated Mar 2026