DSA problem

Gas Station

MediumGreedyPattern: Greedytop150AmazonMicrosoftGoogleBloombergMeta

There are n gas stations along a circular route, where the amount of gas at the i-th station is gas[i]. You have a car with an unlimited gas tank, and it costs cost[i] of gas to travel from the i-th station to its next (i + 1)-th station. You begin the journey with an empty tank at one of the gas stations. Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

A first observation cuts the problem in half: if the total gas across all stations is less than the total cost, then no matter where you start the trip ends in failure. Otherwise — total gas at least total cost — a valid starting station exists, and the question becomes which one.

The greedy insight is that if you start at station i and the running tank dips below zero at station j, then no station between i and j (inclusive) can be a valid start either. The reason: starting at any of those would either match or fall short of the same balance by the time you reach j. So we restart the search at j + 1 and reset the tank to zero. Combined with the existence guarantee, this restart strategy reveals the unique valid starting index in one linear sweep.

The whole algorithm is a single O(n) pass. We maintain three values: the total surplus across all stations (used to confirm solvability), a running tank starting from the candidate start, and the candidate start index. Space is O(1). This greedy is optimal — the existence and uniqueness guarantees together with the restart lemma prove there is no other candidate to check.

Examples

Example 1

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]

Output: 3

Explanation: Start at index 3 with tank = 0. tank = 0 + 4 - 1 = 3 → arrive at 4. tank = 3 + 5 - 2 = 6 → arrive at 0. tank = 6 + 1 - 3 = 4 → arrive at 1. tank = 4 + 2 - 4 = 2 → arrive at 2. tank = 2 + 3 - 5 = 0 → back at 3, full circle complete.

Example 2

Input: gas = [2,3,4], cost = [3,4,3]

Output: -1

Explanation: Total gas = 9, total cost = 10. Demand exceeds supply, so no starting station can complete the circuit.

Example 3

Input: gas = [5,1,2,3,4], cost = [4,4,1,5,1]

Output: 4

Explanation: Total gas = 15 ≥ total cost = 15. The greedy restart finds the unique valid start at index 4 in one pass.

Constraints

n == gas.length == cost.length
1 <= n <= 10^5
0 <= gas[i], cost[i] <= 10^4
The input is generated such that the answer is unique.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

greedyarrayprefix-sum

Browse all DSA problems