Gas Station

greedyarray

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)