Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Gas Station

LeetCode #134Medium
If total gas ≥ total cost, one start works — find it

Given gas available at each station along a circular route and the cost to travel from each station to the next, return the starting station index from which you can complete the full loop, or -1 if no such start exists. A unique answer is guaranteed when one exists.

Asked atAmazonGoogleMicrosoft
step 1 / 12
1
2
3
4
5
[0][1][2][3][4]
cost
3
4
5
1
2
[0][1][2][3][4]
Greedy · one pass, reset start past each failure
▸
1given gas, cost
2total ← 0; tank ← 0; start ← 0
3for i ← 0 to n − 1:
4    d ← gas[i] − cost[i]
5    total += d; tank += d
6    if tank < 0:           // segment start..i unusable
7        start ← i + 1; tank ← 0
8return total ≥ 0 ? start : −1
state
  • gas[1, 2, 3, 4, 5]
  • cost[3, 4, 5, 1, 2]

line 1Circular route of 5 stations. gas[i] = fuel you gain at station i, cost[i] = fuel to drive from i to i+1. Start with an empty tank at some station and find an index you can begin at to complete the full loop — or report −1.