134. Gas Station - Detailed Explanation

Problem Statement

You are given two integer arrays, gas and cost, both of length n. There are n gas stations arranged in a circle. At station i, you can obtain gas[i] units of fuel. It costs cost[i] units of fuel to travel from station i to station (i + 1) mod n. You start with an empty gas tank at one of the gas stations. Your task is to return the starting gas station's index if you can travel around the circuit once (completing a full circle), otherwise return -1.

Example Inputs & Outputs

• Example 1:
  Input:

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

  Output: 3
  Explanation:

  • Start at station 3:
    • Fuel available = 4; cost to go to station 4 = 1; remaining fuel = 3.
    • At station 4, add gas = 5; fuel becomes 8; cost to station 0 = 2; remaining fuel = 6.
    • At station 0, add gas = 1; fuel becomes 7; cost to station 1 = 3; remaining fuel = 4.
    • At station 1, add gas = 2; fuel becomes 6; cost to station 2 = 4; remaining fuel = 2.
    • At station 2, add gas = 3; fuel becomes 5; cost to station 3 = 5; remaining fuel = 0.
    • The journey is completed, returning to station 3.

• Example 2:
  Input:

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

  Output: -1
  Explanation:

  • Total gas = 2 + 3 + 4 = 9; total cost = 3 + 4 + 3 = 10.
  • Since the overall gas is less than the overall cost, it is impossible to complete the circuit.

Constraints

• The length of gas and cost arrays is the same (n ≥ 1).
• 0 ≤ gas[i], cost[i] ≤ 10⁴.
• The solution must determine if a complete circuit is possible and, if so, identify the starting station index.

Hints

1. Check Overall Feasibility:
   Before trying to find a starting station, compare the total gas available with the total cost required. If total gas is less than total cost, it’s impossible to complete the circuit.

2. Greedy Approach with Running Tank:
   As you iterate over the gas stations, keep track of the current fuel balance. When the fuel balance becomes negative, it means you cannot reach the next station starting from the current candidate—so, reset the candidate to the next station.

Approaches

1. Brute Force Approach

Idea:

• For every station, simulate the journey around the circuit starting from that station.
• Check if the fuel never drops below zero during the trip.
• Return the first station where the simulation succeeds.

Drawbacks:

• The brute force approach requires simulating a full circuit for each starting station, leading to a time complexity of O(n²), which is impractical for large inputs.

2. Optimal Greedy Approach

Key Observations:

• If the total gas is less than the total cost, no solution exists.
• If you start at a station and at some point your fuel balance drops below zero, then none of the stations between your start and that point can be the valid starting point. You can then jump to the next station after the failure point.

Algorithm Steps:

1. Check Total Feasibility:
   Sum all gas and cost values. If total_gas < total_cost, return -1.

2. Iterate and Track Fuel Balance:

   • Initialize start = 0 and currentTank = 0.
   • For each station i, update currentTank += gas[i] - cost[i].
   • If currentTank becomes negative, set start = i + 1 and reset currentTank = 0.

3. Return start:
   After the loop, start will be the candidate starting station that can complete the circuit.

Visual Walkthrough (Example 1: [1,2,3,4,5] & [3,4,5,1,2]):

• Station 0:
  Fuel difference = 1 - 3 = -2
  currentTank becomes negative → cannot start at 0. Set start = 1, reset currentTank = 0.

• Station 1:
  Fuel difference = 2 - 4 = -2
  currentTank negative again → cannot start at 1. Set start = 2, reset currentTank = 0.

• Station 2:
  Fuel difference = 3 - 5 = -2
  currentTank negative → set start = 3, reset currentTank = 0.

• Station 3:
  Fuel difference = 4 - 1 = +3
  currentTank becomes 3 → continue.

• Station 4:
  Fuel difference = 5 - 2 = +3
  currentTank becomes 6 → complete the loop.

Since the total gas is greater than or equal to total cost, starting at station 3 allows you to complete the circuit.

Code Implementations

Python Code