Coding Interview PatternsGas Station
MediumGreedy Techniques

Gas Station

Explanation & Solution

Practice Problem

Description

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

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

Input:gas = [1,2,3,4,5], cost = [3,4,5,1,2]
0
1
1
2
2
3
3
4
4
5
0
3
1
4
2
5
3
1
4
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. Tank = 5 - 5 = 0. You can complete the circuit starting from index 3.

Constraints

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

Approach

Greedy Techniques pattern

1. Check Feasibility with Total Gas

  • Sum up the net gain (gas[i] - cost[i]) across all stations into totalTank
  • If totalTank < 0, the total gas available is less than the total cost — completing the circuit is impossible, so return -1

2. Track the Current Tank

  • Maintain a currentTank variable that accumulates the net gain as you move forward from a candidate starting station
  • If currentTank drops below 0 at station i, it means you cannot reach station i + 1 starting from the current candidate

3. Reset the Starting Station

  • When currentTank < 0, discard all stations from the current start up to i — none of them can be valid starting points
  • Set start = i + 1 and reset currentTank = 0 to begin evaluating the next candidate

4. Return the Answer

  • After the loop, if totalTank >= 0, a valid circuit exists and start holds the correct index
  • If totalTank < 0, return -1

Key Insight

  • The greedy approach works because if the total gas is at least the total cost, a solution is guaranteed to exist (and is unique)
  • By resetting the start whenever the tank runs dry, we efficiently eliminate all invalid candidates in a single pass
Time
O(n)one pass through the arrays
Space
O(1)only three variables used

Solution Code

Previous
Best Time to Buy and Sell Stock II
Next
Candy