Gas Station

01 · Question

There are n gas stations. You have two integer arrays gas and cost. Return the starting gas station index if you can travel around the circuit once, otherwise return -1.

02 · Analysis

gas[i] is available fuel at station i and cost[i] is fuel needed to reach the next station, wrapping around. Start with an empty unlimited tank; arrays have equal positive length and nonnegative entries. If candidate start s first has a negative balance at i, any later start through i also fails there, since removing a nonnegative earlier prefix cannot improve a negative balance. Restart at i+1. Separately, a negative total makes every start impossible. O(n) time, O(1) space; return any valid start when ties are allowed.

03 · Solution

Reference solution

1def canCompleteCircuit(gas: List[int], cost: List[int]) -> int:
2    if sum(gas) < sum(cost):
3        return -1
4
5    start = 0
6    tank = 0
7    for i in range(len(gas)):
8        tank += gas[i] - cost[i]
9        if tank < 0:
10            start = i + 1
11            tank = 0
12    return start

Jump Game II

Most Non-overlapping Intervals