Gas Station

Problem Statement

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 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.

Examples

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 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Constraints

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

Approach

Key Insight

Greedy approach is optimal!

Two crucial observations:

1. If the total gas ≥ total cost, a solution exists
2. If you can't reach station j from station i, then you can't reach j from any station between i and j

Greedy Solution (Optimal)

Track current gas tank and reset start position when we run out of gas.

Algorithm:

1. Initialize:

   • totalGas = 0, totalCost = 0 (to check if solution exists)
   • currentGas = 0 (current tank)
   • startStation = 0 (potential starting station)

2. For each station i:

   • Add gas[i] to both totalGas and currentGas
   • Add cost[i] to both totalCost and subtract from currentGas
   • If currentGas < 0:
     • We can't reach next station from current start
     • Set startStation = i + 1
     • Reset currentGas = 0

3. Return totalGas >= totalCost ? startStation : -1

Why This Works:

Key Insight: If we can't reach station j from station i, then we also can't reach j from any station between i and j.

Proof:

• Suppose we start at station i and run out of gas before reaching station j
• This means: sum(gas[i..j-1]) < sum(cost[i..j-1])
• For any station k where i < k < j:
  • Starting at k means we have less accumulated gas than if we started at i
  • Because we already used gas to get from i to k
  • So if i can't reach j, neither can k

Therefore, when we fail to reach a station, we can skip all intermediate stations and try the next one.

Alternative: Brute Force

Try each station as starting point (O(n²)).

Algorithm:

1. For each station i as potential start: 2. Simulate traveling the entire circuit 3. If we complete the circuit, return i
2. Return -1 if no valid start found

Complexity Analysis

Greedy Solution:

• Time Complexity: O(n) - single pass through all stations
• Space Complexity: O(1) - only constant extra space

Brute Force Solution:

• Time Complexity: O(n²) - try each start, simulate each circuit
• Space Complexity: O(1) - constant space

Pattern Recognition

This problem demonstrates:

• Greedy optimization
• Mathematical insight to prune search space
• Accumulation tracking pattern
• Circular array traversal
• Common interview pattern showing greedy vs brute force trade-offs

Related Problems

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