Back to Problems

Gas Station

Medium
greedy

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith 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.

Greedy Insight: If total gas >= total cost, a solution exists. Start from index 0, track current tank. If tank goes negative at station i, start over from i+1 (all stations 0..i cannot be valid starts).

Why Greedy Works: If we run out of gas at station i starting from station s, then no station between s and i can be a valid starting point (they would all run out at or before i). So we skip to i+1.

Example 1

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation: Start at station 3 (index 3) and fill up with 4 units of gas. Tank = 0 + 4 = 4. Travel to station 4. Tank = 4 - 1 + 5 = 8. Travel to station 0. Tank = 8 - 2 + 1 = 7. Travel to station 1. Tank = 7 - 3 + 2 = 6. Travel to station 2. Tank = 6 - 4 + 3 = 5. Travel to station 3. Cost is 5. Tank is just enough to complete the circuit.

Example 2

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation: Total gas = 9, total cost = 10. You cannot complete the circuit.

Constraints

  • •n == gas.length == cost.length
  • •1 <= n <= 10^5
  • •0 <= gas[i], cost[i] <= 10^4
Show Hints (4)
Hint 1: If total gas < total cost, it's impossible to complete the circuit.
Hint 2: If you can't reach station i from start s, then no station between s and i can be a valid start.
Hint 3: Reset the start to i+1 and current tank to 0 when you run out of gas.
Hint 4: If total gas >= total cost, the start we find must be valid.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?