What it teaches: Reset the start after any failing stretch; a non-negative total guarantees success.
Practise it on judges as “Gas Station”.
The problem
On a circular route, station i gives gas[i] and driving to the next costs cost[i]. Return the starting station that lets you complete the circuit (unique if it exists), or −1.
Example 1
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Constraints
1 ≤ n ≤ 10⁵
Pattern clues in the wording
→ Circular running total
→ Find a start that never goes negative
These clues point to Greedy Choice: Make the best-looking choice at each step and never undo it, after proving that this choice is always safe.
Stuck? Take one hint at a time
Solution.java · starter
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
return -1;
}
}
Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
tank and total accumulate gas − cost; when tank < 0, start = i + 1 and tank = 0.
Approach 1
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) { start = i + 1; tank = 0; }
}
return total >= 0 ? start : -1;
}
}
Verdict: The reset argument makes it linear.
Before you submit
Edge cases and common mistakes
Test these inputs
Single station
Total exactly zero
Mistakes people make
Simulating from every station (O(n²)).
Interview
Follow-up questions
Why does the final start complete the whole circle?