Graphs/Cheapest Flights Within K StopsMedium

This practice workspace is built for desktop. Open it on a larger screen to start solving.

Cheapest Flights Within K Stops

Graphs·Medium

There are n cities connected by some flights. You are given an array flights where flights[i] = [from, to, price]. Given integers src, dst, and k, return the cheapest price from src to dst with at most k stops. Return -1 if there is no such route.

A route with k stops uses exactly k + 1 flights (edges). Use Bellman-Ford with at most k + 1 relaxation rounds, or a modified Dijkstra that tracks the number of stops.

Examples

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1

Output: 200

Cheapest route with at most 1 stop: 0->1->2 costs 100+100=200.

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0

Output: 500

Only direct flight 0->2 is allowed (0 stops).

Constraints

1 <= n <= 100
0 <= flights.length <= n * (n - 1) / 2
flights[i].length == 3
0 <= from, to < n
from != to
1 <= price <= 10000
0 <= k < n

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Graphs
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.