This problem follows the Circular Greedy pattern, commonly found in the Greedy category. Recognizing this pattern is key to solving it efficiently in an interview setting.
If total gas >= total cost, solution exists. Track running surplus; reset start when it goes negative.
If total gas >= total cost, a solution must exist. The greedy reset works because if you can't reach station i+1 from station j, you can't reach it from any station between j and i either.
if sum(gas) < sum(cost): return -1
start = 0
surplus = 0
for i in range(len(gas)):
surplus += gas[i] - cost[i]
if surplus < 0:
start = i + 1
surplus = 0
return startPractice Gas Station and similar Greedy problems with flashcards. Build pattern recognition through active recall.
Practice this problem