Introduction

Gas Station is a classic Greedy Optimization problem.

You are given:

  • gas[i] = amount of gas at station i
  • cost[i] = gas needed to travel to next station

Goal:

Find the starting gas station index from which you can complete the entire circular route.

If impossible, return -1.

Example

Input

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

Output

 3

Explanation

Start at station 3Tank = 4
Travel entire circle
Return back to station 3
Journey completed.

Key Observation

If total gas is less than total cost:

 Answer = -1

If the tank becomes negative at station i:

None of the stations before i can be the answer.

Algorithm

  1. Calculate totalGas and totalCost.
  2. If totalGas < totalCost:
    • Return -1.
  3. Traverse all stations.
  4. Maintain current tank.
  5. If tank becomes negative:
    • Reset starting station.
    • Reset tank.
  6. Return starting station.

Dry Run

Input

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

Station 0

tank = 1 - 3tank = -2
Reset start = 1

Station 1

tank = 2 - 4tank = -2
Reset start = 2

Station 2

tank = 3 - 5tank = -2
Reset start = 3

Station 3

tank = 4 - 1tank = 3

Station 4

tank = 3 + (5 - 2)tank = 6

Answer

3

Approach : Greedy

Whenever the tank becomes negative, discard all previous stations as possible starting points.

The next station becomes the new candidate.

Practice

Complexity Analysis

Time Complexity: O(n)Explanation: The stations are traversed exactly once while maintaining the fuel balance.

Space Complexity: O(1)
Explanation: Only a few variables are used to track the tank and starting station.

Why This Problem is Important

Gas Station is one of the most famous Greedy Optimization problems and teaches how local failures can eliminate multiple candidate solutions.

Common Beginner Mistakes

  • Not checking total gas versus total cost.
  • Trying every station as a starting point.
  • Forgetting to reset the tank.
  • Missing the greedy observation.

Interview Tip

Always mention:

If the tank becomes negative at station i, none of the stations before i can be a valid starting point.

Related Questions

  • Jump Game
  • Jump Game II
  • Best Time to Buy and Sell Stock II
  • Candy
  • Partition Labels

Final Takeaway

Gas Station is a classic greedy problem where we use fuel balance to eliminate impossible starting points. The key observation allows us to solve the problem in O(n) time instead of checking every station.