DSA-143 · FOCUSED PRACTICE
Gas Station
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 66444 deterministic checks. Learner drafts are not executed.
Understand the problem
Stations form a directed cycle. At station i collect gas[i] fuel, then spend cost[i] to move to (i+1) modulo n. Starting with an empty tank of unlimited capacity, return an index from which one full circuit is possible, or −1 if none exists.
- gas and cost are non-null int[] arrays with equal length 0..100000 and nonnegative entries. Null throws NullPointerException; unequal/excessive lengths or a negative entry throw IllegalArgumentException. Both arrays are fully validated before computing a result.
- Empty arrays return −1. A station whose gas covers its own cost is a valid singleton start. Multiple valid starts are permitted; the API promises one valid start, without a uniqueness claim. Zero tank is allowed after any edge.
- Preserve both arrays, including when they are the same object. Fuel collection precedes travel payment, the tank has no capacity limit, and fuel/cost units are exact integers. Track differences, candidate tank, and global total in long; sums may exceed int.
Examples
Input:
gas=[1,2,3,4,5], cost=[3,4,5,1,2]
Output:3Starting at three yields nonnegative tank after each edge and returns to three.
Input:
gas=[2,3,4], cost=[3,4,3]
Output:-1Total available fuel is smaller than total cost.
Input:
gas=[0,0], cost=[0,0]
Output:0Both starts work; the strict-negative reset leaves zero as the selected start.
Before you start
- Prefix sums and signed long arithmetic
- Loop invariants for candidate elimination
Recognize the structure
A failed attempt contains more information than the failure of its first station. If a candidate start survives through index i−1 and first goes negative after i, every start inside that tested segment also fails by i. Eliminate the whole segment and begin at i+1. Keep the global total separately: resetting a local tank must never erase the conservation check for the complete cycle.
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.
No unsaved text changes · 132/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
What condition must total fuel satisfy regardless of the starting station?
Hint 2
If start first fails at i, what balance would a later start inside that segment have at i?
Hint 3
Reset only the local candidate tank, then use total conservation to justify the final wrap.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Try every starting station around the cycle
For each start, simulate up to n collect-and-pay steps in circular order and stop at the first negative tank. Return the first complete simulation or −1. This takes O(n²) worst-case time and constant workspace. Tests independently inspect prefix minima for every rotated sequence, so they validate feasibility without copying the greedy candidate-elimination recurrence. Large stress inputs run only the linear reference.
Improve the baseline
Replace each station by its signed net contribution
Define delta[i]=gas[i]−cost[i], evaluated after widening gas to long. Unlimited capacity makes only this net change relevant to the balance after traversing the outgoing edge. The cumulative total is independent of the chosen rotation and must be nonnegative for any valid circuit.
Maintain a surviving suffix candidate
start names the first station after the last rejected segment. tank is the sum of deltas from start through the current station, while total is the sum from zero through that station. Before a failure, every earlier prefix of the candidate segment was nonnegative.
Discard an entire failed segment
If tank becomes negative at i, a proposed start k within [start,i] has balance sum(start..i)−sum(start..k−1) by i. The first term is negative and the subtracted prefix is nonnegative, so k fails too. Set start=i+1 and tank=0 while leaving total untouched.
Use the global sum to justify the wrapped part
The final surviving start corresponds to the earliest position after a strict new minimum of the ordinary prefix sums. Its suffix has nonnegative partial balances. When it wraps, each balance is total plus a prefix difference from that minimum, which remains nonnegative when total≥0.
Keep zero and numeric extremes precise
Reset only on tank<0; zero is feasible and needs no replacement. At most 100000 valid int contributions give magnitude below 2.15×10^14, within long. Widening before subtraction and accumulation makes this bound apply to actual Java arithmetic.
Why it is correct
Elimination is sound
At a first failure, all candidate-prefix sums before the failing edge are nonnegative. Subtracting any such prefix from the negative full segment cannot make it nonnegative. Every skipped start is therefore impossible, so a successful answer is never discarded.
Nonnegative total is sufficient for the survivor
Let P be the prefix sums with P(0)=0. Strict-negative resets select the position following a new minimum prefix. No later prefix falls below that chosen minimum. Before wrapping, differences from it are nonnegative; after wrapping, the differences gain the nonnegative full total. Every edge of the selected rotation is affordable.
Necessity and termination
A full circuit has the same total change for every rotation. A negative total forbids returning with a nonnegative tank. Otherwise the selected start is inside the array: a reset to n would require the final prefix to be strictly below an already nonpositive minimum, forcing a negative total. A single finite scan returns a feasible index or −1 without modifying inputs.
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.Objects;
public final class Solution {
private Solution() {}
private static void validate(int[] gas, int[] cost) {
Objects.requireNonNull(gas, "gas");
Objects.requireNonNull(cost, "cost");
if (gas.length != cost.length || gas.length > 100_000) throw new IllegalArgumentException("length");
for (int index = 0; index < gas.length; index++) {
if (gas[index] < 0 || cost[index] < 0) throw new IllegalArgumentException("negative fuel");
}
}
public static int canCompleteCircuit(int[] gas, int[] cost) {
validate(gas, cost);
if (gas.length == 0) return -1;
long total = 0, tank = 0;
int start = 0;
for (int index = 0; index < gas.length; index++) {
long delta = (long) gas[index] - cost[index];
total += delta;
tank += delta;
if (tank < 0) {
start = index + 1;
tank = 0;
}
}
return total < 0 ? -1 : start;
}
// Simulate each possible starting station; short inputs only.
public static int baseline(int[] gas, int[] cost) {
validate(gas, cost);
for (int start = 0; start < gas.length; start++) {
long tank = 0;
int steps = 0;
while (steps < gas.length) {
int station = (start + steps) % gas.length;
tank += (long) gas[station] - cost[station];
if (tank < 0) break;
steps++;
}
if (steps == gas.length) return start;
}
return -1;
}
}
Read the meaningful blocks
Validate paired arrays and initialize both balances
The two independent balances begin at zero. Empty input returns −1 before the station scan. A negative trailing entry remains an error even when the prefix already appears impossible.
Accumulate each delta once in both roles
total represents conservation across the entire input. tank represents only the current candidate segment and can be reset. Sharing their role would make the final global test meaningless.
Return after the global conservation test
The reference does not run a second circular simulation because the minimum-prefix argument already proves it. Tests do run independent full rotations and accept any feasible start under the public contract.
Complexity
The reference validates and scans n stations in O(n) time with O(1) auxiliary space. All balances fit signed long under the documented bounds. It does not build a doubled array, prefix-sum array, or list of rejected starts.
The baseline uses O(n²) worst-case time and O(1) space. Trace cards may retain rejected segments and prefix histories for explanation; these histories are excluded from the reference workspace.
Exact-state walkthroughs
Reveal normal and boundary traces
Repeated elimination followed by a successful wrap
Input: {"gas":[1,2,3,4,5],"cost":[3,4,5,1,2]} · One feasible starting station / −1: 3
Step 1 of 11: Begin an empty local candidate and an independent global total.
Fuel is collected before paying an edge. The tank has unlimited capacity; zero balance is permitted.
Phase: initial.
Read-only station net changes
- 0: collect 1, pay 3, delta -2
- 1: collect 2, pay 4, delta -2
- 2: collect 3, pay 5, delta -2
- 3: collect 4, pay 1, delta 3
- 4: collect 5, pay 2, delta 3
Separate live balances
- global total: 0
- candidate start: 0
- candidate tank: 0
Rejected inclusive start segments
Empty.
Ordinary global prefix sums — teaching history
- P(0)=0
A failed segment eliminates all its interior starts. Nonnegative total justifies the surviving start across the wrapped prefix. Zero balance is allowed; the tank has unlimited capacity. Java uses long balances.
| Variable | Value |
|---|---|
| input | {"gas":[1,2,3,4,5],"cost":[3,4,5,1,2]} |
| phase | "initial" |
| total | 0 |
| tank | 0 |
| start | 0 |
| rejected | [] |
| prefix | [0] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] gas, int[] cost) { 6 Objects.requireNonNull(gas, "gas"); 7 Objects.requireNonNull(cost, "cost"); 8 if (gas.length != cost.length || gas.length > 100_000) throw new IllegalArgumentException("length"); 9 for (int index = 0; index < gas.length; index++) { 10 if (gas[index] < 0 || cost[index] < 0) throw new IllegalArgumentException("negative fuel"); 11 } 12 } 13 public static int canCompleteCircuit(int[] gas, int[] cost) { 14 validate(gas, cost); 15 if (gas.length == 0) return -1; 16 long total = 0, tank = 0; 17 int start = 0; 18 for (int index = 0; index < gas.length; index++) { 19 long delta = (long) gas[index] - cost[index]; 20 total += delta; 21 tank += delta; 22 if (tank < 0) { 23 start = index + 1; 24 tank = 0; 25 } 26 } 27 return total < 0 ? -1 : start; 28 } 29 // Simulate each possible starting station; short inputs only. 30 public static int baseline(int[] gas, int[] cost) { 31 validate(gas, cost); 32 for (int start = 0; start < gas.length; start++) { 33 long tank = 0; 34 int steps = 0; 35 while (steps < gas.length) { 36 int station = (start + steps) % gas.length; 37 tank += (long) gas[station] - cost[station]; 38 if (tank < 0) break; 39 steps++; 40 } 41 if (steps == gas.length) return start; 42 } 43 return -1; 44 } 45 } 46
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin an empty local candidate and an independent global total.
Fuel is collected before paying an edge. The tank has unlimited capacity; zero balance is permitted.
- input
{"gas":[1,2,3,4,5],"cost":[3,4,5,1,2]}- phase
"initial"- total
0- tank
0- start
0- rejected
[]- prefix
[0]
- Collect and pay for this outgoing edge.
total never forgets a station. tank covers only start..index and is allowed to be temporarily negative before rejection. Java uses long; these fixture values are also exact JavaScript integers.
- input
{"gas":[1,2,3,4,5],"cost":[3,4,5,1,2]}- phase
"station"- total
-2- tank
-2- start
0- rejected
[]- prefix
[0,-2]- index
0- delta
-2
- Eliminate every start in the failed segment.
Every earlier prefix of the segment was nonnegative; subtracting one from its negative full sum cannot rescue an interior start. Only tank resets.
- input
{"gas":[1,2,3,4,5],"cost":[3,4,5,1,2]}- phase
"reset"- total
-2- tank
0- start
1- rejected
[[0,0]]- prefix
[0,-2]- index
0- failedStart
0- failedTank
-2
- Collect and pay for this outgoing edge.
total never forgets a station. tank covers only start..index and is allowed to be temporarily negative before rejection. Java uses long; these fixture values are also exact JavaScript integers.
- input
{"gas":[1,2,3,4,5],"cost":[3,4,5,1,2]}- phase
"station"- total
-4- tank
-2- start
1- rejected
[[0,0]]- prefix
[0,-2,-4]- index
1- delta
-2
- Eliminate every start in the failed segment.
Every earlier prefix of the segment was nonnegative; subtracting one from its negative full sum cannot rescue an interior start. Only tank resets.
- input
{"gas":[1,2,3,4,5],"cost":[3,4,5,1,2]}- phase
"reset"- total
-4- tank
0- start
2- rejected
[[0,0],[1,1]]- prefix
[0,-2,-4]- index
1- failedStart
1- failedTank
-2
- Collect and pay for this outgoing edge.
total never forgets a station. tank covers only start..index and is allowed to be temporarily negative before rejection. Java uses long; these fixture values are also exact JavaScript integers.
- input
{"gas":[1,2,3,4,5],"cost":[3,4,5,1,2]}- phase
"station"- total
-6- tank
-2- start
2- rejected
[[0,0],[1,1]]- prefix
[0,-2,-4,-6]- index
2- delta
-2
- Eliminate every start in the failed segment.
Every earlier prefix of the segment was nonnegative; subtracting one from its negative full sum cannot rescue an interior start. Only tank resets.
- input
{"gas":[1,2,3,4,5],"cost":[3,4,5,1,2]}- phase
"reset"- total
-6- tank
0- start
3- rejected
[[0,0],[1,1],[2,2]]- prefix
[0,-2,-4,-6]- index
2- failedStart
2- failedTank
-2
- Collect and pay for this outgoing edge.
total never forgets a station. tank covers only start..index and is allowed to be temporarily negative before rejection. Java uses long; these fixture values are also exact JavaScript integers.
- input
{"gas":[1,2,3,4,5],"cost":[3,4,5,1,2]}- phase
"station"- total
-3- tank
3- start
3- rejected
[[0,0],[1,1],[2,2]]- prefix
[0,-2,-4,-6,-3]- index
3- delta
3
- Collect and pay for this outgoing edge.
total never forgets a station. tank covers only start..index and is allowed to be temporarily negative before rejection. Java uses long; these fixture values are also exact JavaScript integers.
- input
{"gas":[1,2,3,4,5],"cost":[3,4,5,1,2]}- phase
"station"- total
0- tank
6- start
3- rejected
[[0,0],[1,1],[2,2]]- prefix
[0,-2,-4,-6,-3,0]- index
4- delta
3
- Apply full-cycle fuel conservation.
Nonnegative total makes the surviving minimum-prefix start feasible even after wrapping. Empty input returns −1.
- input
{"gas":[1,2,3,4,5],"cost":[3,4,5,1,2]}- phase
"complete"- total
0- tank
6- start
3- rejected
[[0,0],[1,1],[2,2]]- prefix
[0,-2,-4,-6,-3,0]
- Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
- result
3
A surviving suffix still fails global conservation
Input: {"gas":[2,3,4],"cost":[3,4,3]} · One feasible starting station / −1: -1
Step 1 of 8: Begin an empty local candidate and an independent global total.
Fuel is collected before paying an edge. The tank has unlimited capacity; zero balance is permitted.
Phase: initial.
Read-only station net changes
- 0: collect 2, pay 3, delta -1
- 1: collect 3, pay 4, delta -1
- 2: collect 4, pay 3, delta 1
Separate live balances
- global total: 0
- candidate start: 0
- candidate tank: 0
Rejected inclusive start segments
Empty.
Ordinary global prefix sums — teaching history
- P(0)=0
A failed segment eliminates all its interior starts. Nonnegative total justifies the surviving start across the wrapped prefix. Zero balance is allowed; the tank has unlimited capacity. Java uses long balances.
| Variable | Value |
|---|---|
| input | {"gas":[2,3,4],"cost":[3,4,3]} |
| phase | "initial" |
| total | 0 |
| tank | 0 |
| start | 0 |
| rejected | [] |
| prefix | [0] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] gas, int[] cost) { 6 Objects.requireNonNull(gas, "gas"); 7 Objects.requireNonNull(cost, "cost"); 8 if (gas.length != cost.length || gas.length > 100_000) throw new IllegalArgumentException("length"); 9 for (int index = 0; index < gas.length; index++) { 10 if (gas[index] < 0 || cost[index] < 0) throw new IllegalArgumentException("negative fuel"); 11 } 12 } 13 public static int canCompleteCircuit(int[] gas, int[] cost) { 14 validate(gas, cost); 15 if (gas.length == 0) return -1; 16 long total = 0, tank = 0; 17 int start = 0; 18 for (int index = 0; index < gas.length; index++) { 19 long delta = (long) gas[index] - cost[index]; 20 total += delta; 21 tank += delta; 22 if (tank < 0) { 23 start = index + 1; 24 tank = 0; 25 } 26 } 27 return total < 0 ? -1 : start; 28 } 29 // Simulate each possible starting station; short inputs only. 30 public static int baseline(int[] gas, int[] cost) { 31 validate(gas, cost); 32 for (int start = 0; start < gas.length; start++) { 33 long tank = 0; 34 int steps = 0; 35 while (steps < gas.length) { 36 int station = (start + steps) % gas.length; 37 tank += (long) gas[station] - cost[station]; 38 if (tank < 0) break; 39 steps++; 40 } 41 if (steps == gas.length) return start; 42 } 43 return -1; 44 } 45 } 46
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin an empty local candidate and an independent global total.
Fuel is collected before paying an edge. The tank has unlimited capacity; zero balance is permitted.
- input
{"gas":[2,3,4],"cost":[3,4,3]}- phase
"initial"- total
0- tank
0- start
0- rejected
[]- prefix
[0]
- Collect and pay for this outgoing edge.
total never forgets a station. tank covers only start..index and is allowed to be temporarily negative before rejection. Java uses long; these fixture values are also exact JavaScript integers.
- input
{"gas":[2,3,4],"cost":[3,4,3]}- phase
"station"- total
-1- tank
-1- start
0- rejected
[]- prefix
[0,-1]- index
0- delta
-1
- Eliminate every start in the failed segment.
Every earlier prefix of the segment was nonnegative; subtracting one from its negative full sum cannot rescue an interior start. Only tank resets.
- input
{"gas":[2,3,4],"cost":[3,4,3]}- phase
"reset"- total
-1- tank
0- start
1- rejected
[[0,0]]- prefix
[0,-1]- index
0- failedStart
0- failedTank
-1
- Collect and pay for this outgoing edge.
total never forgets a station. tank covers only start..index and is allowed to be temporarily negative before rejection. Java uses long; these fixture values are also exact JavaScript integers.
- input
{"gas":[2,3,4],"cost":[3,4,3]}- phase
"station"- total
-2- tank
-1- start
1- rejected
[[0,0]]- prefix
[0,-1,-2]- index
1- delta
-1
- Eliminate every start in the failed segment.
Every earlier prefix of the segment was nonnegative; subtracting one from its negative full sum cannot rescue an interior start. Only tank resets.
- input
{"gas":[2,3,4],"cost":[3,4,3]}- phase
"reset"- total
-2- tank
0- start
2- rejected
[[0,0],[1,1]]- prefix
[0,-1,-2]- index
1- failedStart
1- failedTank
-1
- Collect and pay for this outgoing edge.
total never forgets a station. tank covers only start..index and is allowed to be temporarily negative before rejection. Java uses long; these fixture values are also exact JavaScript integers.
- input
{"gas":[2,3,4],"cost":[3,4,3]}- phase
"station"- total
-1- tank
1- start
2- rejected
[[0,0],[1,1]]- prefix
[0,-1,-2,-1]- index
2- delta
1
- Apply full-cycle fuel conservation.
Nonnegative total makes the surviving minimum-prefix start feasible even after wrapping. Empty input returns −1.
- input
{"gas":[2,3,4],"cost":[3,4,3]}- phase
"complete"- total
-1- tank
1- start
2- rejected
[[0,0],[1,1]]- prefix
[0,-1,-2,-1]
- Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
- result
-1
Zero does not require a reset
Input: {"gas":[0,0],"cost":[0,0]} · One feasible starting station / −1: 0
Step 1 of 5: Begin an empty local candidate and an independent global total.
Fuel is collected before paying an edge. The tank has unlimited capacity; zero balance is permitted.
Phase: initial.
Read-only station net changes
- 0: collect 0, pay 0, delta 0
- 1: collect 0, pay 0, delta 0
Separate live balances
- global total: 0
- candidate start: 0
- candidate tank: 0
Rejected inclusive start segments
Empty.
Ordinary global prefix sums — teaching history
- P(0)=0
A failed segment eliminates all its interior starts. Nonnegative total justifies the surviving start across the wrapped prefix. Zero balance is allowed; the tank has unlimited capacity. Java uses long balances.
| Variable | Value |
|---|---|
| input | {"gas":[0,0],"cost":[0,0]} |
| phase | "initial" |
| total | 0 |
| tank | 0 |
| start | 0 |
| rejected | [] |
| prefix | [0] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] gas, int[] cost) { 6 Objects.requireNonNull(gas, "gas"); 7 Objects.requireNonNull(cost, "cost"); 8 if (gas.length != cost.length || gas.length > 100_000) throw new IllegalArgumentException("length"); 9 for (int index = 0; index < gas.length; index++) { 10 if (gas[index] < 0 || cost[index] < 0) throw new IllegalArgumentException("negative fuel"); 11 } 12 } 13 public static int canCompleteCircuit(int[] gas, int[] cost) { 14 validate(gas, cost); 15 if (gas.length == 0) return -1; 16 long total = 0, tank = 0; 17 int start = 0; 18 for (int index = 0; index < gas.length; index++) { 19 long delta = (long) gas[index] - cost[index]; 20 total += delta; 21 tank += delta; 22 if (tank < 0) { 23 start = index + 1; 24 tank = 0; 25 } 26 } 27 return total < 0 ? -1 : start; 28 } 29 // Simulate each possible starting station; short inputs only. 30 public static int baseline(int[] gas, int[] cost) { 31 validate(gas, cost); 32 for (int start = 0; start < gas.length; start++) { 33 long tank = 0; 34 int steps = 0; 35 while (steps < gas.length) { 36 int station = (start + steps) % gas.length; 37 tank += (long) gas[station] - cost[station]; 38 if (tank < 0) break; 39 steps++; 40 } 41 if (steps == gas.length) return start; 42 } 43 return -1; 44 } 45 } 46
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin an empty local candidate and an independent global total.
Fuel is collected before paying an edge. The tank has unlimited capacity; zero balance is permitted.
- input
{"gas":[0,0],"cost":[0,0]}- phase
"initial"- total
0- tank
0- start
0- rejected
[]- prefix
[0]
- Collect and pay for this outgoing edge.
total never forgets a station. tank covers only start..index and is allowed to be temporarily negative before rejection. Java uses long; these fixture values are also exact JavaScript integers.
- input
{"gas":[0,0],"cost":[0,0]}- phase
"station"- total
0- tank
0- start
0- rejected
[]- prefix
[0,0]- index
0- delta
0
- Collect and pay for this outgoing edge.
total never forgets a station. tank covers only start..index and is allowed to be temporarily negative before rejection. Java uses long; these fixture values are also exact JavaScript integers.
- input
{"gas":[0,0],"cost":[0,0]}- phase
"station"- total
0- tank
0- start
0- rejected
[]- prefix
[0,0,0]- index
1- delta
0
- Apply full-cycle fuel conservation.
Nonnegative total makes the surviving minimum-prefix start feasible even after wrapping. Empty input returns −1.
- input
{"gas":[0,0],"cost":[0,0]}- phase
"complete"- total
0- tank
0- start
0- rejected
[]- prefix
[0,0,0]
- Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
- result
0
Long balance beyond int
Input: {"gas":[2147483647,2147483647,0],"cost":[0,0,2147483647]} · One feasible starting station / −1: 0
Step 1 of 6: Begin an empty local candidate and an independent global total.
Fuel is collected before paying an edge. The tank has unlimited capacity; zero balance is permitted.
Phase: initial.
Read-only station net changes
- 0: collect 2147483647, pay 0, delta 2147483647
- 1: collect 2147483647, pay 0, delta 2147483647
- 2: collect 0, pay 2147483647, delta -2147483647
Separate live balances
- global total: 0
- candidate start: 0
- candidate tank: 0
Rejected inclusive start segments
Empty.
Ordinary global prefix sums — teaching history
- P(0)=0
A failed segment eliminates all its interior starts. Nonnegative total justifies the surviving start across the wrapped prefix. Zero balance is allowed; the tank has unlimited capacity. Java uses long balances.
| Variable | Value |
|---|---|
| input | {"gas":[2147483647,2147483647,0],"cost":[0,0,2147483647]} |
| phase | "initial" |
| total | 0 |
| tank | 0 |
| start | 0 |
| rejected | [] |
| prefix | [0] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] gas, int[] cost) { 6 Objects.requireNonNull(gas, "gas"); 7 Objects.requireNonNull(cost, "cost"); 8 if (gas.length != cost.length || gas.length > 100_000) throw new IllegalArgumentException("length"); 9 for (int index = 0; index < gas.length; index++) { 10 if (gas[index] < 0 || cost[index] < 0) throw new IllegalArgumentException("negative fuel"); 11 } 12 } 13 public static int canCompleteCircuit(int[] gas, int[] cost) { 14 validate(gas, cost); 15 if (gas.length == 0) return -1; 16 long total = 0, tank = 0; 17 int start = 0; 18 for (int index = 0; index < gas.length; index++) { 19 long delta = (long) gas[index] - cost[index]; 20 total += delta; 21 tank += delta; 22 if (tank < 0) { 23 start = index + 1; 24 tank = 0; 25 } 26 } 27 return total < 0 ? -1 : start; 28 } 29 // Simulate each possible starting station; short inputs only. 30 public static int baseline(int[] gas, int[] cost) { 31 validate(gas, cost); 32 for (int start = 0; start < gas.length; start++) { 33 long tank = 0; 34 int steps = 0; 35 while (steps < gas.length) { 36 int station = (start + steps) % gas.length; 37 tank += (long) gas[station] - cost[station]; 38 if (tank < 0) break; 39 steps++; 40 } 41 if (steps == gas.length) return start; 42 } 43 return -1; 44 } 45 } 46
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin an empty local candidate and an independent global total.
Fuel is collected before paying an edge. The tank has unlimited capacity; zero balance is permitted.
- input
{"gas":[2147483647,2147483647,0],"cost":[0,0,2147483647]}- phase
"initial"- total
0- tank
0- start
0- rejected
[]- prefix
[0]
- Collect and pay for this outgoing edge.
total never forgets a station. tank covers only start..index and is allowed to be temporarily negative before rejection. Java uses long; these fixture values are also exact JavaScript integers.
- input
{"gas":[2147483647,2147483647,0],"cost":[0,0,2147483647]}- phase
"station"- total
2147483647- tank
2147483647- start
0- rejected
[]- prefix
[0,2147483647]- index
0- delta
2147483647
- Collect and pay for this outgoing edge.
total never forgets a station. tank covers only start..index and is allowed to be temporarily negative before rejection. Java uses long; these fixture values are also exact JavaScript integers.
- input
{"gas":[2147483647,2147483647,0],"cost":[0,0,2147483647]}- phase
"station"- total
4294967294- tank
4294967294- start
0- rejected
[]- prefix
[0,2147483647,4294967294]- index
1- delta
2147483647
- Collect and pay for this outgoing edge.
total never forgets a station. tank covers only start..index and is allowed to be temporarily negative before rejection. Java uses long; these fixture values are also exact JavaScript integers.
- input
{"gas":[2147483647,2147483647,0],"cost":[0,0,2147483647]}- phase
"station"- total
2147483647- tank
2147483647- start
0- rejected
[]- prefix
[0,2147483647,4294967294,2147483647]- index
2- delta
-2147483647
- Apply full-cycle fuel conservation.
Nonnegative total makes the surviving minimum-prefix start feasible even after wrapping. Empty input returns −1.
- input
{"gas":[2147483647,2147483647,0],"cost":[0,0,2147483647]}- phase
"complete"- total
2147483647- tank
2147483647- start
0- rejected
[]- prefix
[0,2147483647,4294967294,2147483647]
- Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
- result
0
No stations
Input: {"gas":[],"cost":[]} · One feasible starting station / −1: -1
Step 1 of 3: Begin an empty local candidate and an independent global total.
Fuel is collected before paying an edge. The tank has unlimited capacity; zero balance is permitted.
Phase: initial.
Read-only station net changes
Empty.
Separate live balances
- global total: 0
- candidate start: 0
- candidate tank: 0
Rejected inclusive start segments
Empty.
Ordinary global prefix sums — teaching history
- P(0)=0
A failed segment eliminates all its interior starts. Nonnegative total justifies the surviving start across the wrapped prefix. Zero balance is allowed; the tank has unlimited capacity. Java uses long balances.
| Variable | Value |
|---|---|
| input | {"gas":[],"cost":[]} |
| phase | "initial" |
| total | 0 |
| tank | 0 |
| start | 0 |
| rejected | [] |
| prefix | [0] |
See the affected Java block
1 import java.util.Objects; 2 3 public final class Solution { 4 private Solution() {} 5 private static void validate(int[] gas, int[] cost) { 6 Objects.requireNonNull(gas, "gas"); 7 Objects.requireNonNull(cost, "cost"); 8 if (gas.length != cost.length || gas.length > 100_000) throw new IllegalArgumentException("length"); 9 for (int index = 0; index < gas.length; index++) { 10 if (gas[index] < 0 || cost[index] < 0) throw new IllegalArgumentException("negative fuel"); 11 } 12 } 13 public static int canCompleteCircuit(int[] gas, int[] cost) { 14 validate(gas, cost); 15 if (gas.length == 0) return -1; 16 long total = 0, tank = 0; 17 int start = 0; 18 for (int index = 0; index < gas.length; index++) { 19 long delta = (long) gas[index] - cost[index]; 20 total += delta; 21 tank += delta; 22 if (tank < 0) { 23 start = index + 1; 24 tank = 0; 25 } 26 } 27 return total < 0 ? -1 : start; 28 } 29 // Simulate each possible starting station; short inputs only. 30 public static int baseline(int[] gas, int[] cost) { 31 validate(gas, cost); 32 for (int start = 0; start < gas.length; start++) { 33 long tank = 0; 34 int steps = 0; 35 while (steps < gas.length) { 36 int station = (start + steps) % gas.length; 37 tank += (long) gas[station] - cost[station]; 38 if (tank < 0) break; 39 steps++; 40 } 41 if (steps == gas.length) return start; 42 } 43 return -1; 44 } 45 } 46
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin an empty local candidate and an independent global total.
Fuel is collected before paying an edge. The tank has unlimited capacity; zero balance is permitted.
- input
{"gas":[],"cost":[]}- phase
"initial"- total
0- tank
0- start
0- rejected
[]- prefix
[0]
- Apply full-cycle fuel conservation.
Nonnegative total makes the surviving minimum-prefix start feasible even after wrapping. Empty input returns −1.
- input
{"gas":[],"cost":[]}- phase
"complete"- total
0- tank
0- start
0- rejected
[]- prefix
[0]
- Return the documented outcome.
The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.
- result
-1
Test the contract
Input:
gas=[], cost=[]
Output:-1No station.
Input:
gas=[5], cost=[5]
Output:0Zero ending tank is feasible.
Input:
gas=[1], cost=[2]
Output:-1Negative full total.
Input:
gas=[0,0,5], cost=[1,1,1]
Output:2Two starts are eliminated before the positive suffix.
Input:
gas=[2147483647,2147483647,0], cost=[0,0,2147483647]
Output:0Intermediate balance exceeds int.
Input:
gas=[1], cost=[]
Output:IllegalArgumentExceptionLengths must agree.
Common mistakes and counterexamples
Reset the global total with the candidate tank
Counterexample: gas=[1,0], cost=[0,2] has negative total even after the local tank resets.
Reset tank alone; total always contains every processed delta.
Skip only the failing station without a segment proof
Counterexample: Many intermediate candidates can be tested redundantly.
Use the nonnegative-prefix subtraction argument to reject the whole failed segment.
Reject a zero tank or assume a unique solution
Counterexample: All-zero arrays permit every start.
Use a strict-negative reset and promise a valid index rather than uniqueness.
Use int for fuel balances
Counterexample: Two MAX_VALUE fuel entries already exceed the positive int range.
Widen before subtraction and accumulate in long.
Follow-ups
Return every feasible start.
The one-candidate state intentionally discards information. Use prefix sums of a doubled delta sequence and a sliding-window minimum: a start is feasible when its next n prefix values never fall below its starting prefix. A monotonic deque can process the windows in linear time.
Impose a finite tank capacity.
Net sums alone no longer capture overflowed fuel that was discarded at a station. Re-derive the feasibility state with capacity and collection timing; the unlimited-tank elimination proof cannot simply be cited.
Require a minimum initial fuel amount.
For a fixed start, it is max(0,−minimum prefix balance of its rotated route). To optimize across starts, use cyclic prefix minima with an explicit numeric bound and deterministic ties.