DSA-114 · Frozen shortest-path layers indexed by a capped edge budget

Cheapest Flights Within K Stops

Advanced · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 1067886 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the cheapest directed flight cost from source to target using at most k intermediate stops, or −1 if no such route exists. A route with h flights has h−1 intermediate stops; the empty route costs zero when source equals target.

n is a positive vertex count; vertices are 0..n−1, including isolated vertices. source must be in that range. edges is a nonnull int[][] of nonnull triples [from,to,weight]. Edges are directed; self-loops, repeated rows, parallel edges, and zero weights are valid. Null outer input throws NullPointerException; malformed triples, invalid labels, or forbidden weights throw IllegalArgumentException before traversal. Prices span 0..Integer.MAX_VALUE. target is a valid vertex and k is any nonnegative int; invalid target or negative k throws IllegalArgumentException. Size preconditions are n≤1,000 and at most 10,000 flight occurrences.
cheapestFlight returns long; −1 denotes infeasibility. At most k stops permits at most k+1 edges. With nonnegative prices, removing cycles never increases price or edge usage, so cap the actual edge budget at n−1. Compute k+1 in long before clamping, including k=Integer.MAX_VALUE.
Preserve source values and row identities, including shared row objects. No sorting or marking may alter the caller’s arrays. Auxiliary graph entries are privately allocated. Input must not be modified concurrently. Input edge order must not affect the answer. Zero-price cycles and parallel fares remain valid; no negative prices are supported.

Examples

Input: n=3, edges=[[0,1,1],[1,2,1],[0,2,8]], source=0, target=2, k=0
Output: 8
One allowed flight excludes the cheaper two-flight route.
Input: Same flights, k=1
Output: 2
One intermediate stop admits 0→1→2.
Input: source=target, any nonnegative k
Output: 0
The empty route wins or ties because all prices are nonnegative.

Before you start

At-most versus exact-edge dynamic programming
Why remaining budget belongs in a constrained path state

Recognize the structure

A cheap arrival at a city can consume more flights than a costly arrival and leave too little budget to finish. Therefore one global cheapest label per city plus ordinary Dijkstra finality is insufficient. Make the allowed edge count an explicit DP dimension. Frozen rolling arrays evaluate that dimension without a heap or a full budget-by-vertex table.

Try before revealing

Hint 1

Count flights rather than stops and define a budget-indexed distance.

Hint 2

How can a whole round guarantee it adds at most one edge?

Hint 3

Clone the old layer, read only that layer for every relaxation, and cap the nonnegative budget at n−1.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate all bounded flight walks

Build outgoing lists and recursively try every outgoing occurrence while the remaining edge allowance is positive. Reaching the target can return immediately: continuing through nonnegative cycles cannot improve that candidate. Cap the allowance using the same cycle-removal argument. This compiling baseline explores routes rather than sharing subproblems and is used only on small harness inputs; deep recursion and branching make it unsuitable for production bounds.

Improve the baseline

Define the exact meaning of a layer

Let D_r(v) be the cheapest cost to v using at most r flights. D_0(source)=0 and all other values are infinite. The answer is D_B(target), where B=min(k+1,n−1). This is a path in the layered state graph, whose transitions always advance the layer even if the original graph cycles.

Read old values and write into a clone

The recurrence is D_r(v)=min(D_(r−1)(v), min over u→v of D_(r−1)(u)+price). Cloning previous preserves routes that already use fewer flights. Read only previous[tail] during the entire flight scan; next is a collection of candidate improvements, never a source for the same round.

Commit complete rounds and stop at a fixed point

After every edge occurrence is considered, next becomes previous. If no value changed, applying the same monotone recurrence again will reproduce it, so further rounds are unnecessary. Read the target after complete rounds and translate infinity into −1. A reachable target does not justify early exit if later allowed layers can lower its cost.

Why it is correct

Base case and recurrence

A route using at most r flights either already uses at most r−1, or has a final edge u→v whose prefix uses at most r−1. These two exhaustive cases give the recurrence. Conversely each finite recurrence candidate is an actual permitted route, so the minimum is both attainable and optimal.

Rolling storage preserves the budget

Inductively previous equals D_(r−1). Every edge read uses that unchanged array; writing a better next value cannot affect any later read this round. After the scan next equals D_r independent of input ordering. In-place updates would instead permit arbitrarily many edges within one scan.

Budget cap and stability are sound

Any repeated vertex on a feasible walk bounds a directed cycle of nonnegative total price. Deleting it yields a no-more-expensive feasible walk with fewer edges. Thus some optimum is simple, using at most n−1 edges. A full unchanged round is a fixed point of the same recurrence, so no later round can improve it.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    private static void validate(int n,int[][] edges,int source) {
        Objects.requireNonNull(edges,"edges");
        if(n<1||source<0||source>=n)throw new IllegalArgumentException("invalid universe or source");
        for(int[] e:edges)if(e==null||e.length!=3||e[0]<0||e[0]>=n||e[1]<0||e[1]>=n||e[2]<0)throw new IllegalArgumentException("invalid weighted edge");
    }
    public static long cheapestFlight(int n,int[][] edges,int source,int target,int k) {
        validate(n,edges,source);if(target<0||target>=n||k<0)throw new IllegalArgumentException("invalid target or stop budget");
        int budget=(int)Math.min((long)k+1,n-1L);
        long[] previous=new long[n];Arrays.fill(previous,Long.MAX_VALUE);previous[source]=0;
        for(int round=1;round<=budget;round++) {
            long[] next=previous.clone();
            for(int[] edge:edges)if(previous[edge[0]]!=Long.MAX_VALUE) {
                long candidate=previous[edge[0]]+edge[2];
                if(candidate<next[edge[1]])next[edge[1]]=candidate;
            }
            boolean stable=Arrays.equals(previous,next);previous=next;
            if(stable)break;
        }
        return previous[target]==Long.MAX_VALUE?-1:previous[target];
    }
    private static long enumerate(List<List<int[]>> graph,int v,int target,int left,long cost) {
        if(v==target)return cost;if(left==0)return Long.MAX_VALUE;long best=Long.MAX_VALUE;
        for(int[] e:graph.get(v))best=Math.min(best,enumerate(graph,e[0],target,left-1,cost+e[1]));return best;
    }
    public static long baseline(int n,int[][] edges,int source,int target,int k) {
        validate(n,edges,source);if(target<0||target>=n||k<0)throw new IllegalArgumentException("invalid target or stop budget");
        List<List<int[]>> graph=new ArrayList<>();for(int v=0;v<n;v++)graph.add(new ArrayList<>());for(int[] e:edges)graph.get(e[0]).add(new int[]{e[1],e[2]});
        long result=enumerate(graph,source,target,(int)Math.min((long)k+1,n-1L),0);return result==Long.MAX_VALUE?-1:result;
    }
}

Read the meaningful blocks

Clone means at most, not exactly

Starting next as all-infinite computes exactly r flights unless the recurrence explicitly carries previous values. The clone keeps the source’s zero-edge route and any cheaper shorter itinerary. The independent test oracle deliberately uses exact-edge tables and minimizes across lengths to check the alternate formulation.

Stop count is not an edge count

A direct flight has zero intermediate stops but still consumes one edge. A source-to-itself query needs no flights. Cast k before addition: (long)k+1 avoids a negative budget from int overflow.

Avoid city-only dominance

Consider a city reached cheaply after two flights and expensively after one. With one flight still needed to target and a two-flight total limit, only the expensive arrival can finish. The rolling arrays retain the right prefix optimum separately at every allowed edge layer rather than discarding useful states globally.

Complexity

Let V=n, E be flights, and B=min((long)k+1,V−1). Main time is O(V+E+B(V+E)): validate, initialize, then clone V labels and scan E occurrences per round. Auxiliary live storage is O(V) for two long arrays; no adjacency list is needed. Old arrays become collectible; total allocation across all rounds can be O(BV) despite O(V) simultaneous workspace. Output is one long.

The recursive baseline builds O(V+E) adjacency storage and uses O(B+1) call depth. With maximum outgoing occurrence count Δ, a safe bound is O(V+E+V·(Δ+1)^(B+1)) time, deliberately loose for all degenerate cases. It is exponential and may overflow the stack at deep budgets; the shipped main loop is iterative. Teaching trace histories retain every flight scan and are excluded from these runtime bounds.

Exact-state walkthroughs

Reveal normal and boundary traces

One stop limit separates frozen reads from tentative writes

Input: {"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":0} · Minimum fare within stop limit / −1: 8

Step 1 of 8: Seed the zero-edge layer at the source.

previous[v] is the cheapest cost with at most the committed number of edges. Infinity is displayed as null; the Java sentinel is Long.MAX_VALUE.

Limited stops — frozen old costs and the next edge layer

Phase: initial.

Source 0 → target 2. At most 0 intermediate stops; capped flight budget 1. Zero-edge layer.

Directed flights — source → destination : price

0: 0 → 1 : 1
1: 1 → 2 : 1
2: 0 → 2 : 8

Two different layers — reads stay frozen for the whole scan

vertex 0previous: 0next: no uncommitted layer
vertex 1previous: ∞ (no finite label)next: no uncommitted layer
vertex 2previous: ∞ (no finite label)next: no uncommitted layer

Cloning carries shorter routes forward. A value written to next cannot feed another flight during the same round. Large stop budgets clamp only because prices are nonnegative.

∞ is displayed as null in the exact state table and means Java Long.MAX_VALUE. Final unreachable results use −1. Input values and row identities stay unchanged. Histories and logical frontier pictures are teaching views, excluded from Java workspace.

State after this step
Variable	Value
input	`{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":0}`
budget	`1`
previous	`[0,null,null]`
next	`null`
phase	`"initial"`
round	`0`
edgeIndex	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int n,int[][] edges,int source) {
 4         Objects.requireNonNull(edges,"edges");
 5         if(n<1||source<0||source>=n)throw new IllegalArgumentException("invalid universe or source");
 6         for(int[] e:edges)if(e==null||e.length!=3||e[0]<0||e[0]>=n||e[1]<0||e[1]>=n||e[2]<0)throw new IllegalArgumentException("invalid weighted edge");
 7     }
 8     public static long cheapestFlight(int n,int[][] edges,int source,int target,int k) {
 9         validate(n,edges,source);if(target<0||target>=n||k<0)throw new IllegalArgumentException("invalid target or stop budget");
10         int budget=(int)Math.min((long)k+1,n-1L);
11         long[] previous=new long[n];Arrays.fill(previous,Long.MAX_VALUE);previous[source]=0;
12         for(int round=1;round<=budget;round++) {
13             long[] next=previous.clone();
14             for(int[] edge:edges)if(previous[edge[0]]!=Long.MAX_VALUE) {
15                 long candidate=previous[edge[0]]+edge[2];
16                 if(candidate<next[edge[1]])next[edge[1]]=candidate;
17             }
18             boolean stable=Arrays.equals(previous,next);previous=next;
19             if(stable)break;
20         }
21         return previous[target]==Long.MAX_VALUE?-1:previous[target];
22     }
23     private static long enumerate(List<List<int[]>> graph,int v,int target,int left,long cost) {
24         if(v==target)return cost;if(left==0)return Long.MAX_VALUE;long best=Long.MAX_VALUE;
25         for(int[] e:graph.get(v))best=Math.min(best,enumerate(graph,e[0],target,left-1,cost+e[1]));return best;
26     }
27     public static long baseline(int n,int[][] edges,int source,int target,int k) {
28         validate(n,edges,source);if(target<0||target>=n||k<0)throw new IllegalArgumentException("invalid target or stop budget");
29         List<List<int[]>> graph=new ArrayList<>();for(int v=0;v<n;v++)graph.add(new ArrayList<>());for(int[] e:edges)graph.get(e[0]).add(new int[]{e[1],e[2]});
30         long result=enumerate(graph,source,target,(int)Math.min((long)k+1,n-1L),0);return result==Long.MAX_VALUE?-1:result;
31     }
32 }
33

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed the zero-edge layer at the source.
previous[v] is the cheapest cost with at most the committed number of edges. Infinity is displayed as null; the Java sentinel is Long.MAX_VALUE.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":0}
budget
1
previous
[0,null,null]
next
null
phase
"initial"
round
0
edgeIndex
null
Clone the frozen previous layer before scanning any flights.
Carrying old values forward means at most, not exactly, this many edges. Reads must use previous throughout this round.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":0}
budget
1
previous
[0,null,null]
next
[0,null,null]
phase
"round"
round
1
edgeIndex
null
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":0}
budget
1
previous
[0,null,null]
next
[0,1,null]
phase
"flight"
round
1
edgeIndex
0
candidate
1
improved
true
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":0}
budget
1
previous
[0,null,null]
next
[0,1,null]
phase
"flight"
round
1
edgeIndex
1
candidate
null
improved
false
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":0}
budget
1
previous
[0,null,null]
next
[0,1,8]
phase
"flight"
round
1
edgeIndex
2
candidate
8
improved
true
Commit this complete edge-budget layer.
A fixed point cannot improve in later rounds. With nonnegative prices a cheapest walk can discard cycles, so at most n−1 edges suffice even when k is Integer.MAX_VALUE.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":0}
budget
1
previous
[0,1,8]
next
null
phase
"commit"
round
1
edgeIndex
null
stable
false
Read the target only after complete rounds.
k counts intermediate stops, so the unbounded input allowance is k+1 edges. Source equal to target retains the zero-edge cost zero.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":0}
budget
1
previous
[0,1,8]
next
null
phase
"complete"
edgeIndex
null
Return the documented result without changing caller input.
Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.
result
8

A second round admits the cheaper connection

Input: {"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":1} · Minimum fare within stop limit / −1: 2

Step 1 of 13: Seed the zero-edge layer at the source.

previous[v] is the cheapest cost with at most the committed number of edges. Infinity is displayed as null; the Java sentinel is Long.MAX_VALUE.

Limited stops — frozen old costs and the next edge layer

Phase: initial.

Source 0 → target 2. At most 1 intermediate stops; capped flight budget 2. Zero-edge layer.

Directed flights — source → destination : price

0: 0 → 1 : 1
1: 1 → 2 : 1
2: 0 → 2 : 8

Two different layers — reads stay frozen for the whole scan

vertex 0previous: 0next: no uncommitted layer
vertex 1previous: ∞ (no finite label)next: no uncommitted layer
vertex 2previous: ∞ (no finite label)next: no uncommitted layer

Cloning carries shorter routes forward. A value written to next cannot feed another flight during the same round. Large stop budgets clamp only because prices are nonnegative.

State after this step
Variable	Value
input	`{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":1}`
budget	`2`
previous	`[0,null,null]`
next	`null`
phase	`"initial"`
round	`0`
edgeIndex	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int n,int[][] edges,int source) {
 4         Objects.requireNonNull(edges,"edges");
 5         if(n<1||source<0||source>=n)throw new IllegalArgumentException("invalid universe or source");
 6         for(int[] e:edges)if(e==null||e.length!=3||e[0]<0||e[0]>=n||e[1]<0||e[1]>=n||e[2]<0)throw new IllegalArgumentException("invalid weighted edge");
 7     }
 8     public static long cheapestFlight(int n,int[][] edges,int source,int target,int k) {
 9         validate(n,edges,source);if(target<0||target>=n||k<0)throw new IllegalArgumentException("invalid target or stop budget");
10         int budget=(int)Math.min((long)k+1,n-1L);
11         long[] previous=new long[n];Arrays.fill(previous,Long.MAX_VALUE);previous[source]=0;
12         for(int round=1;round<=budget;round++) {
13             long[] next=previous.clone();
14             for(int[] edge:edges)if(previous[edge[0]]!=Long.MAX_VALUE) {
15                 long candidate=previous[edge[0]]+edge[2];
16                 if(candidate<next[edge[1]])next[edge[1]]=candidate;
17             }
18             boolean stable=Arrays.equals(previous,next);previous=next;
19             if(stable)break;
20         }
21         return previous[target]==Long.MAX_VALUE?-1:previous[target];
22     }
23     private static long enumerate(List<List<int[]>> graph,int v,int target,int left,long cost) {
24         if(v==target)return cost;if(left==0)return Long.MAX_VALUE;long best=Long.MAX_VALUE;
25         for(int[] e:graph.get(v))best=Math.min(best,enumerate(graph,e[0],target,left-1,cost+e[1]));return best;
26     }
27     public static long baseline(int n,int[][] edges,int source,int target,int k) {
28         validate(n,edges,source);if(target<0||target>=n||k<0)throw new IllegalArgumentException("invalid target or stop budget");
29         List<List<int[]>> graph=new ArrayList<>();for(int v=0;v<n;v++)graph.add(new ArrayList<>());for(int[] e:edges)graph.get(e[0]).add(new int[]{e[1],e[2]});
30         long result=enumerate(graph,source,target,(int)Math.min((long)k+1,n-1L),0);return result==Long.MAX_VALUE?-1:result;
31     }
32 }
33

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed the zero-edge layer at the source.
previous[v] is the cheapest cost with at most the committed number of edges. Infinity is displayed as null; the Java sentinel is Long.MAX_VALUE.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":1}
budget
2
previous
[0,null,null]
next
null
phase
"initial"
round
0
edgeIndex
null
Clone the frozen previous layer before scanning any flights.
Carrying old values forward means at most, not exactly, this many edges. Reads must use previous throughout this round.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":1}
budget
2
previous
[0,null,null]
next
[0,null,null]
phase
"round"
round
1
edgeIndex
null
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":1}
budget
2
previous
[0,null,null]
next
[0,1,null]
phase
"flight"
round
1
edgeIndex
0
candidate
1
improved
true
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":1}
budget
2
previous
[0,null,null]
next
[0,1,null]
phase
"flight"
round
1
edgeIndex
1
candidate
null
improved
false
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":1}
budget
2
previous
[0,null,null]
next
[0,1,8]
phase
"flight"
round
1
edgeIndex
2
candidate
8
improved
true
Commit this complete edge-budget layer.
A fixed point cannot improve in later rounds. With nonnegative prices a cheapest walk can discard cycles, so at most n−1 edges suffice even when k is Integer.MAX_VALUE.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":1}
budget
2
previous
[0,1,8]
next
null
phase
"commit"
round
1
edgeIndex
null
stable
false
Clone the frozen previous layer before scanning any flights.
Carrying old values forward means at most, not exactly, this many edges. Reads must use previous throughout this round.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":1}
budget
2
previous
[0,1,8]
next
[0,1,8]
phase
"round"
round
2
edgeIndex
null
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":1}
budget
2
previous
[0,1,8]
next
[0,1,8]
phase
"flight"
round
2
edgeIndex
0
candidate
1
improved
false
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":1}
budget
2
previous
[0,1,8]
next
[0,1,2]
phase
"flight"
round
2
edgeIndex
1
candidate
2
improved
true
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":1}
budget
2
previous
[0,1,8]
next
[0,1,2]
phase
"flight"
round
2
edgeIndex
2
candidate
8
improved
false
Commit this complete edge-budget layer.
A fixed point cannot improve in later rounds. With nonnegative prices a cheapest walk can discard cycles, so at most n−1 edges suffice even when k is Integer.MAX_VALUE.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":1}
budget
2
previous
[0,1,2]
next
null
phase
"commit"
round
2
edgeIndex
null
stable
false
Read the target only after complete rounds.
k counts intermediate stops, so the unbounded input allowance is k+1 edges. Source equal to target retains the zero-edge cost zero.
input
{"n":3,"edges":[[0,1,1],[1,2,1],[0,2,8]],"source":0,"target":2,"k":1}
budget
2
previous
[0,1,2]
next
null
phase
"complete"
edgeIndex
null
Return the documented result without changing caller input.
Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.
result
2

Unreachable destination and a zero-price cycle

Input: {"n":4,"edges":[[0,1,0],[1,0,0],[2,3,2]],"source":0,"target":3,"k":8} · Minimum fare within stop limit / −1: -1

Step 1 of 13: Seed the zero-edge layer at the source.

previous[v] is the cheapest cost with at most the committed number of edges. Infinity is displayed as null; the Java sentinel is Long.MAX_VALUE.

Limited stops — frozen old costs and the next edge layer

Phase: initial.

Source 0 → target 3. At most 8 intermediate stops; capped flight budget 3. Zero-edge layer.

Directed flights — source → destination : price

0: 0 → 1 : 0
1: 1 → 0 : 0
2: 2 → 3 : 2

Two different layers — reads stay frozen for the whole scan

vertex 0previous: 0next: no uncommitted layer
vertex 1previous: ∞ (no finite label)next: no uncommitted layer
vertex 2previous: ∞ (no finite label)next: no uncommitted layer
vertex 3previous: ∞ (no finite label)next: no uncommitted layer

Cloning carries shorter routes forward. A value written to next cannot feed another flight during the same round. Large stop budgets clamp only because prices are nonnegative.

State after this step
Variable	Value
input	`{"n":4,"edges":[[0,1,0],[1,0,0],[2,3,2]],"source":0,"target":3,"k":8}`
budget	`3`
previous	`[0,null,null,null]`
next	`null`
phase	`"initial"`
round	`0`
edgeIndex	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int n,int[][] edges,int source) {
 4         Objects.requireNonNull(edges,"edges");
 5         if(n<1||source<0||source>=n)throw new IllegalArgumentException("invalid universe or source");
 6         for(int[] e:edges)if(e==null||e.length!=3||e[0]<0||e[0]>=n||e[1]<0||e[1]>=n||e[2]<0)throw new IllegalArgumentException("invalid weighted edge");
 7     }
 8     public static long cheapestFlight(int n,int[][] edges,int source,int target,int k) {
 9         validate(n,edges,source);if(target<0||target>=n||k<0)throw new IllegalArgumentException("invalid target or stop budget");
10         int budget=(int)Math.min((long)k+1,n-1L);
11         long[] previous=new long[n];Arrays.fill(previous,Long.MAX_VALUE);previous[source]=0;
12         for(int round=1;round<=budget;round++) {
13             long[] next=previous.clone();
14             for(int[] edge:edges)if(previous[edge[0]]!=Long.MAX_VALUE) {
15                 long candidate=previous[edge[0]]+edge[2];
16                 if(candidate<next[edge[1]])next[edge[1]]=candidate;
17             }
18             boolean stable=Arrays.equals(previous,next);previous=next;
19             if(stable)break;
20         }
21         return previous[target]==Long.MAX_VALUE?-1:previous[target];
22     }
23     private static long enumerate(List<List<int[]>> graph,int v,int target,int left,long cost) {
24         if(v==target)return cost;if(left==0)return Long.MAX_VALUE;long best=Long.MAX_VALUE;
25         for(int[] e:graph.get(v))best=Math.min(best,enumerate(graph,e[0],target,left-1,cost+e[1]));return best;
26     }
27     public static long baseline(int n,int[][] edges,int source,int target,int k) {
28         validate(n,edges,source);if(target<0||target>=n||k<0)throw new IllegalArgumentException("invalid target or stop budget");
29         List<List<int[]>> graph=new ArrayList<>();for(int v=0;v<n;v++)graph.add(new ArrayList<>());for(int[] e:edges)graph.get(e[0]).add(new int[]{e[1],e[2]});
30         long result=enumerate(graph,source,target,(int)Math.min((long)k+1,n-1L),0);return result==Long.MAX_VALUE?-1:result;
31     }
32 }
33

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed the zero-edge layer at the source.
previous[v] is the cheapest cost with at most the committed number of edges. Infinity is displayed as null; the Java sentinel is Long.MAX_VALUE.
input
{"n":4,"edges":[[0,1,0],[1,0,0],[2,3,2]],"source":0,"target":3,"k":8}
budget
3
previous
[0,null,null,null]
next
null
phase
"initial"
round
0
edgeIndex
null
Clone the frozen previous layer before scanning any flights.
Carrying old values forward means at most, not exactly, this many edges. Reads must use previous throughout this round.
input
{"n":4,"edges":[[0,1,0],[1,0,0],[2,3,2]],"source":0,"target":3,"k":8}
budget
3
previous
[0,null,null,null]
next
[0,null,null,null]
phase
"round"
round
1
edgeIndex
null
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":4,"edges":[[0,1,0],[1,0,0],[2,3,2]],"source":0,"target":3,"k":8}
budget
3
previous
[0,null,null,null]
next
[0,0,null,null]
phase
"flight"
round
1
edgeIndex
0
candidate
0
improved
true
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":4,"edges":[[0,1,0],[1,0,0],[2,3,2]],"source":0,"target":3,"k":8}
budget
3
previous
[0,null,null,null]
next
[0,0,null,null]
phase
"flight"
round
1
edgeIndex
1
candidate
null
improved
false
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":4,"edges":[[0,1,0],[1,0,0],[2,3,2]],"source":0,"target":3,"k":8}
budget
3
previous
[0,null,null,null]
next
[0,0,null,null]
phase
"flight"
round
1
edgeIndex
2
candidate
null
improved
false
Commit this complete edge-budget layer.
A fixed point cannot improve in later rounds. With nonnegative prices a cheapest walk can discard cycles, so at most n−1 edges suffice even when k is Integer.MAX_VALUE.
input
{"n":4,"edges":[[0,1,0],[1,0,0],[2,3,2]],"source":0,"target":3,"k":8}
budget
3
previous
[0,0,null,null]
next
null
phase
"commit"
round
1
edgeIndex
null
stable
false
Clone the frozen previous layer before scanning any flights.
Carrying old values forward means at most, not exactly, this many edges. Reads must use previous throughout this round.
input
{"n":4,"edges":[[0,1,0],[1,0,0],[2,3,2]],"source":0,"target":3,"k":8}
budget
3
previous
[0,0,null,null]
next
[0,0,null,null]
phase
"round"
round
2
edgeIndex
null
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":4,"edges":[[0,1,0],[1,0,0],[2,3,2]],"source":0,"target":3,"k":8}
budget
3
previous
[0,0,null,null]
next
[0,0,null,null]
phase
"flight"
round
2
edgeIndex
0
candidate
0
improved
false
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":4,"edges":[[0,1,0],[1,0,0],[2,3,2]],"source":0,"target":3,"k":8}
budget
3
previous
[0,0,null,null]
next
[0,0,null,null]
phase
"flight"
round
2
edgeIndex
1
candidate
0
improved
false
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":4,"edges":[[0,1,0],[1,0,0],[2,3,2]],"source":0,"target":3,"k":8}
budget
3
previous
[0,0,null,null]
next
[0,0,null,null]
phase
"flight"
round
2
edgeIndex
2
candidate
null
improved
false
Commit this complete edge-budget layer.
A fixed point cannot improve in later rounds. With nonnegative prices a cheapest walk can discard cycles, so at most n−1 edges suffice even when k is Integer.MAX_VALUE.
input
{"n":4,"edges":[[0,1,0],[1,0,0],[2,3,2]],"source":0,"target":3,"k":8}
budget
3
previous
[0,0,null,null]
next
null
phase
"commit"
round
2
edgeIndex
null
stable
true
Read the target only after complete rounds.
k counts intermediate stops, so the unbounded input allowance is k+1 edges. Source equal to target retains the zero-edge cost zero.
input
{"n":4,"edges":[[0,1,0],[1,0,0],[2,3,2]],"source":0,"target":3,"k":8}
budget
3
previous
[0,0,null,null]
next
null
phase
"complete"
edgeIndex
null
Return the documented result without changing caller input.
Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.
result
-1

MAX stop budget safely clamps to a simple path

Input: {"n":3,"edges":[[0,1,2147483647],[1,2,2147483647]],"source":0,"target":2,"k":2147483647} · Minimum fare within stop limit / −1: 4294967294

Step 1 of 11: Seed the zero-edge layer at the source.

previous[v] is the cheapest cost with at most the committed number of edges. Infinity is displayed as null; the Java sentinel is Long.MAX_VALUE.

Limited stops — frozen old costs and the next edge layer

Phase: initial.

Source 0 → target 2. At most 2147483647 intermediate stops; capped flight budget 2. Zero-edge layer.

Directed flights — source → destination : price

0: 0 → 1 : 2147483647
1: 1 → 2 : 2147483647

Two different layers — reads stay frozen for the whole scan

vertex 0previous: 0next: no uncommitted layer
vertex 1previous: ∞ (no finite label)next: no uncommitted layer
vertex 2previous: ∞ (no finite label)next: no uncommitted layer

Cloning carries shorter routes forward. A value written to next cannot feed another flight during the same round. Large stop budgets clamp only because prices are nonnegative.

State after this step
Variable	Value
input	`{"n":3,"edges":[[0,1,2147483647],[1,2,2147483647]],"source":0,"target":2,"k":2147483647}`
budget	`2`
previous	`[0,null,null]`
next	`null`
phase	`"initial"`
round	`0`
edgeIndex	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int n,int[][] edges,int source) {
 4         Objects.requireNonNull(edges,"edges");
 5         if(n<1||source<0||source>=n)throw new IllegalArgumentException("invalid universe or source");
 6         for(int[] e:edges)if(e==null||e.length!=3||e[0]<0||e[0]>=n||e[1]<0||e[1]>=n||e[2]<0)throw new IllegalArgumentException("invalid weighted edge");
 7     }
 8     public static long cheapestFlight(int n,int[][] edges,int source,int target,int k) {
 9         validate(n,edges,source);if(target<0||target>=n||k<0)throw new IllegalArgumentException("invalid target or stop budget");
10         int budget=(int)Math.min((long)k+1,n-1L);
11         long[] previous=new long[n];Arrays.fill(previous,Long.MAX_VALUE);previous[source]=0;
12         for(int round=1;round<=budget;round++) {
13             long[] next=previous.clone();
14             for(int[] edge:edges)if(previous[edge[0]]!=Long.MAX_VALUE) {
15                 long candidate=previous[edge[0]]+edge[2];
16                 if(candidate<next[edge[1]])next[edge[1]]=candidate;
17             }
18             boolean stable=Arrays.equals(previous,next);previous=next;
19             if(stable)break;
20         }
21         return previous[target]==Long.MAX_VALUE?-1:previous[target];
22     }
23     private static long enumerate(List<List<int[]>> graph,int v,int target,int left,long cost) {
24         if(v==target)return cost;if(left==0)return Long.MAX_VALUE;long best=Long.MAX_VALUE;
25         for(int[] e:graph.get(v))best=Math.min(best,enumerate(graph,e[0],target,left-1,cost+e[1]));return best;
26     }
27     public static long baseline(int n,int[][] edges,int source,int target,int k) {
28         validate(n,edges,source);if(target<0||target>=n||k<0)throw new IllegalArgumentException("invalid target or stop budget");
29         List<List<int[]>> graph=new ArrayList<>();for(int v=0;v<n;v++)graph.add(new ArrayList<>());for(int[] e:edges)graph.get(e[0]).add(new int[]{e[1],e[2]});
30         long result=enumerate(graph,source,target,(int)Math.min((long)k+1,n-1L),0);return result==Long.MAX_VALUE?-1:result;
31     }
32 }
33

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed the zero-edge layer at the source.
previous[v] is the cheapest cost with at most the committed number of edges. Infinity is displayed as null; the Java sentinel is Long.MAX_VALUE.
input
{"n":3,"edges":[[0,1,2147483647],[1,2,2147483647]],"source":0,"target":2,"k":2147483647}
budget
2
previous
[0,null,null]
next
null
phase
"initial"
round
0
edgeIndex
null
Clone the frozen previous layer before scanning any flights.
Carrying old values forward means at most, not exactly, this many edges. Reads must use previous throughout this round.
input
{"n":3,"edges":[[0,1,2147483647],[1,2,2147483647]],"source":0,"target":2,"k":2147483647}
budget
2
previous
[0,null,null]
next
[0,null,null]
phase
"round"
round
1
edgeIndex
null
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":3,"edges":[[0,1,2147483647],[1,2,2147483647]],"source":0,"target":2,"k":2147483647}
budget
2
previous
[0,null,null]
next
[0,2147483647,null]
phase
"flight"
round
1
edgeIndex
0
candidate
2147483647
improved
true
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":3,"edges":[[0,1,2147483647],[1,2,2147483647]],"source":0,"target":2,"k":2147483647}
budget
2
previous
[0,null,null]
next
[0,2147483647,null]
phase
"flight"
round
1
edgeIndex
1
candidate
null
improved
false
Commit this complete edge-budget layer.
A fixed point cannot improve in later rounds. With nonnegative prices a cheapest walk can discard cycles, so at most n−1 edges suffice even when k is Integer.MAX_VALUE.
input
{"n":3,"edges":[[0,1,2147483647],[1,2,2147483647]],"source":0,"target":2,"k":2147483647}
budget
2
previous
[0,2147483647,null]
next
null
phase
"commit"
round
1
edgeIndex
null
stable
false
Clone the frozen previous layer before scanning any flights.
Carrying old values forward means at most, not exactly, this many edges. Reads must use previous throughout this round.
input
{"n":3,"edges":[[0,1,2147483647],[1,2,2147483647]],"source":0,"target":2,"k":2147483647}
budget
2
previous
[0,2147483647,null]
next
[0,2147483647,null]
phase
"round"
round
2
edgeIndex
null
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":3,"edges":[[0,1,2147483647],[1,2,2147483647]],"source":0,"target":2,"k":2147483647}
budget
2
previous
[0,2147483647,null]
next
[0,2147483647,null]
phase
"flight"
round
2
edgeIndex
0
candidate
2147483647
improved
false
Consider one flight using only the frozen layer.
An unreachable tail does nothing. Edge order cannot leak an extra flight into this round, and parallel flights are separate candidates.
input
{"n":3,"edges":[[0,1,2147483647],[1,2,2147483647]],"source":0,"target":2,"k":2147483647}
budget
2
previous
[0,2147483647,null]
next
[0,2147483647,4294967294]
phase
"flight"
round
2
edgeIndex
1
candidate
4294967294
improved
true
Commit this complete edge-budget layer.
A fixed point cannot improve in later rounds. With nonnegative prices a cheapest walk can discard cycles, so at most n−1 edges suffice even when k is Integer.MAX_VALUE.
input
{"n":3,"edges":[[0,1,2147483647],[1,2,2147483647]],"source":0,"target":2,"k":2147483647}
budget
2
previous
[0,2147483647,4294967294]
next
null
phase
"commit"
round
2
edgeIndex
null
stable
false
Read the target only after complete rounds.
k counts intermediate stops, so the unbounded input allowance is k+1 edges. Source equal to target retains the zero-edge cost zero.
input
{"n":3,"edges":[[0,1,2147483647],[1,2,2147483647]],"source":0,"target":2,"k":2147483647}
budget
2
previous
[0,2147483647,4294967294]
next
null
phase
"complete"
edgeIndex
null
Return the documented result without changing caller input.
Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.
result
4294967294

Single source-target vertex needs no flight

Input: {"n":1,"edges":[],"source":0,"target":0,"k":2147483647} · Minimum fare within stop limit / −1: 0

Step 1 of 3: Seed the zero-edge layer at the source.

previous[v] is the cheapest cost with at most the committed number of edges. Infinity is displayed as null; the Java sentinel is Long.MAX_VALUE.

Limited stops — frozen old costs and the next edge layer

Phase: initial.

Source 0 → target 0. At most 2147483647 intermediate stops; capped flight budget 0. Zero-edge layer.

Directed flights — source → destination : price

Empty.

Two different layers — reads stay frozen for the whole scan

vertex 0previous: 0next: no uncommitted layer

Cloning carries shorter routes forward. A value written to next cannot feed another flight during the same round. Large stop budgets clamp only because prices are nonnegative.

State after this step
Variable	Value
input	`{"n":1,"edges":[],"source":0,"target":0,"k":2147483647}`
budget	`0`
previous	`[0]`
next	`null`
phase	`"initial"`
round	`0`
edgeIndex	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int n,int[][] edges,int source) {
 4         Objects.requireNonNull(edges,"edges");
 5         if(n<1||source<0||source>=n)throw new IllegalArgumentException("invalid universe or source");
 6         for(int[] e:edges)if(e==null||e.length!=3||e[0]<0||e[0]>=n||e[1]<0||e[1]>=n||e[2]<0)throw new IllegalArgumentException("invalid weighted edge");
 7     }
 8     public static long cheapestFlight(int n,int[][] edges,int source,int target,int k) {
 9         validate(n,edges,source);if(target<0||target>=n||k<0)throw new IllegalArgumentException("invalid target or stop budget");
10         int budget=(int)Math.min((long)k+1,n-1L);
11         long[] previous=new long[n];Arrays.fill(previous,Long.MAX_VALUE);previous[source]=0;
12         for(int round=1;round<=budget;round++) {
13             long[] next=previous.clone();
14             for(int[] edge:edges)if(previous[edge[0]]!=Long.MAX_VALUE) {
15                 long candidate=previous[edge[0]]+edge[2];
16                 if(candidate<next[edge[1]])next[edge[1]]=candidate;
17             }
18             boolean stable=Arrays.equals(previous,next);previous=next;
19             if(stable)break;
20         }
21         return previous[target]==Long.MAX_VALUE?-1:previous[target];
22     }
23     private static long enumerate(List<List<int[]>> graph,int v,int target,int left,long cost) {
24         if(v==target)return cost;if(left==0)return Long.MAX_VALUE;long best=Long.MAX_VALUE;
25         for(int[] e:graph.get(v))best=Math.min(best,enumerate(graph,e[0],target,left-1,cost+e[1]));return best;
26     }
27     public static long baseline(int n,int[][] edges,int source,int target,int k) {
28         validate(n,edges,source);if(target<0||target>=n||k<0)throw new IllegalArgumentException("invalid target or stop budget");
29         List<List<int[]>> graph=new ArrayList<>();for(int v=0;v<n;v++)graph.add(new ArrayList<>());for(int[] e:edges)graph.get(e[0]).add(new int[]{e[1],e[2]});
30         long result=enumerate(graph,source,target,(int)Math.min((long)k+1,n-1L),0);return result==Long.MAX_VALUE?-1:result;
31     }
32 }
33

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed the zero-edge layer at the source.
previous[v] is the cheapest cost with at most the committed number of edges. Infinity is displayed as null; the Java sentinel is Long.MAX_VALUE.
input
{"n":1,"edges":[],"source":0,"target":0,"k":2147483647}
budget
0
previous
[0]
next
null
phase
"initial"
round
0
edgeIndex
null
Read the target only after complete rounds.
k counts intermediate stops, so the unbounded input allowance is k+1 edges. Source equal to target retains the zero-edge cost zero.
input
{"n":1,"edges":[],"source":0,"target":0,"k":2147483647}
budget
0
previous
[0]
next
null
phase
"complete"
edgeIndex
null
Return the documented result without changing caller input.
Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.
result
0

Test the contract

Input: Two-edge cheap path with k=0
Output: direct fare or −1
Exposes in-place budget leakage.
Input: Zero-price cycle and large k
Output: finite nonnegative optimum
Tests cycle removal and safe capping.
Input: Source equals target, n=1, MAX k
Output: 0
Budget becomes zero without overflow.
Input: Two MAX-priced flights
Output: 4294967294 when permitted
Cumulative fare uses long.
Input: Permutation of flights and aliased rows
Output: same result and unchanged input
Rounds are order independent.

Common mistakes and counterexamples

Relax in place

Counterexample: With edges 0→1 then 1→2, k=0 must not use both in one pass.

Read previous and write next, then commit once per complete round.

Stop as soon as target is reachable

Counterexample: A direct fare 8 is reachable in round one, but two flights cost 2 when allowed.

Only stop at a full fixed point or after the budget is exhausted.

Clamp k+1 after int addition

Counterexample: Integer.MAX_VALUE+1 wraps negative.

Promote k before addition and cap with n−1L.

Apply one visited flag per city

Counterexample: A cheap but budget-exhausted arrival can hide a feasible expensive prefix.

Include the budget dimension or prove a valid resource dominance relation.

Follow-ups

Reconstruct an optimal itinerary.

Keep predecessor decisions per budget layer, including carry decisions, or recompute layers during reconstruction. Two rolling arrays alone discard the historical choices. Define tie behavior and include O(BV) history or recomputation cost.

Allow negative fares with a finite stop bound.

The layered recurrence still works for a finite budget, but the simple-path cap at n−1 and immediate target return in the baseline become invalid. Cycles can lower price while consuming budget, and the budget may be huge.

Use a heap with cost and flights used.

Keep separate labels per resource state or a carefully maintained Pareto frontier. A popped state at one flight count does not dominate every state at that city. Compare its state count and memory with the O(V) rolling recurrence.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 203/20,000 characters

Self-review

Can I write the at-most recurrence and prove its carry term?Can I demonstrate why an in-place scan violates k=0?Can I state which nonnegative assumption permits budget capping and early baseline target return?

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform parity claims.