Gas Station
Problem
There are n gas stations along a circular route, where gas[i] is the amount of gas at station i, and cost[i] is the gas needed to travel from station i to station i+1. Starting with an empty tank at one station, return the starting station's index if you can travel around the circuit once, or -1 if it's impossible. If a solution exists, it's guaranteed unique.
Examples
Example 1
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation: Starting at station 3: tank=4-1+5=8, -2+1=7... you can complete the full circuit.
Example 2
Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation: Total gas (9) < total cost (10) — no starting point works.
Constraints
- •
n == gas.length == cost.length - •
1 <= n <= 10^5 - •
0 <= gas[i], cost[i] <= 10^4
Hints
Hint 1
The brute force: try every possible starting station, simulate the full circuit from there, and check if the tank ever goes negative — O(n^2).
Hint 2
If starting at station S causes the tank to go negative by the time you reach station F, no station BETWEEN S and F can be a valid start either — can you see why?
Hint 3
This means you never need to re-simulate from those in-between stations — jump your candidate start straight to the station after the failure point.
Solutions
public int canCompleteCircuitBruteForce(int[] gas, int[] cost) {
int n = gas.length;
for (int start = 0; start < n; start++) {
int tank = 0;
boolean completesCircuit = true;
for (int i = 0; i < n; i++) {
int station = (start + i) % n;
tank += gas[station] - cost[station];
if (tank < 0) { completesCircuit = false; break; }
}
if (completesCircuit) return start;
}
return -1;
}Time: O(n^2) · Space: O(1)