noodleProblems/
Gas Station
#158

Gas Station

AlgorithmmediumArrayGreedy

There are n gas stations arranged in a circle, numbered 0 to n - 1. You're given two integer arrays gas and cost, both of length n: gas[i] is the amount of gas available at station i, and cost[i] is the amount of gas needed to travel from station i to station i + 1 (the last station wraps around to station 0).

You begin with an empty tank at a station of your choosing. Return the index of the starting station that lets you travel around the entire circuit once in the forward direction without the tank ever going negative, or -1 if no such station exists.

It is guaranteed that if a valid starting station exists, it is unique.

Example cases

  • unique feasible start
    in gas = [1,2,3,4,5], cost = [3,4,5,1,2]
    out 3
    Starting at station 3: tank goes 4 -> 4+5-2=7 -> 7+1-3=5 -> 5+2-4=3 -> 3+3-5=1, completing the loop without going negative.
  • impossible
    in gas = [2,3,4], cost = [3,4,3]
    out -1
    Total gas (9) is less than total cost (10), so no starting station can complete the circuit.
  • single station
    in gas = [5], cost = [4]
    out 0
    One station with enough gas to cover its own cost back to itself.

Constraints

  • n == gas.length == cost.length
  • 1 <= n <= 10^5
  • 0 <= gas[i], cost[i] <= 10^4
Saved
gas =
[1,2,3,4,5]
cost =
[3,4,5,1,2]