Gas Stations

Problem Link

Gas Station – LeetCode

Problem: Gas Station

Problem Statement

There are n gas stations arranged in a circle. You are given two integer arrays gas and cost, where:

• gas[i] is the amount of gas available at the i-th station.

• cost[i] is the amount of gas required to travel from the i-th station to the (i+1)-th station (the last station wraps to the first).

Given these two arrays, return the starting gas station's index from which you can travel around the circuit once in the clockwise direction. If it is not possible, return -1.

Examples

Example 1
Input:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (gas = 4),

• Go to station 4 → gas left = 4 - 1 = 3 → +5 = 8

• Go to station 0 → 8 - 2 = 6 → +1 = 7

• Go to station 1 → 7 - 3 = 4 → +2 = 6

• Go to station 2 → 6 - 4 = 2 → +3 = 5

• Go to station 3 → 5 - 5 = 0

Example 2
Input:
gas = [2,3,4]
cost = [3,4,3]
Output: -1
Explanation: It's not possible to complete the circuit from any station.

Constraints

• 1 <= gas.length <= 10⁵

• 0 <= gas[i], cost[i] <= 10⁴

Intuition

To successfully complete the circuit, the total amount of gas across all stations must be greater than or equal to the total cost to travel the entire loop. If this condition fails, return -1.

If the condition passes, then the problem reduces to finding the right starting station. We simulate the journey and track the current tank balance. If at any point this balance goes negative, the journey from the current start is not possible, and we move the start to the next station.

Approach

1. Compute the total gas and total cost. If total gas < total cost, return -1.

2. Initialize:

   • total = 0 → represents current net gas while simulating trip.

   • start = 0 → index of current candidate starting station.

3. Traverse each station i from 0 to n-1:

   • Update total += gas[i] - cost[i].

   • If total < 0, it means we can't reach the next station:

     • Set start = i + 1.

     • Reset total = 0.

4. After traversal, return start.

Code (Java)

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int tGas = 0;
        int tCost = 0;
        int n = gas.length;

        // Step 1: Check if solution exists
        for (int i = 0; i < n; i++) {
            tGas += gas[i];
            tCost += cost[i];
        }
        if (tGas < tCost) return -1;

        // Step 2: Find the correct starting point
        int total = 0;
        int start = 0;
        for (int i = 0; i < n; i++) {
            total += gas[i] - cost[i];
            if (total < 0) {
                total = 0;
                start = i + 1;
            }
        }

        return start;
    }
}

Time and Space Complexity

• Time Complexity: O(n)

  • We traverse the array once to compute total gas and cost.

  • We do another single pass to find the starting index.

• Space Complexity: O(1)

  • Only constant extra space is used.

Dry Run

Input:

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

• Total gas = 15

• Total cost = 15

• net = [ -2, -2, -2, 3, 3 ]

Simulation:

• i = 0: total = -2 → start = 1

• i = 1: total = -2 → start = 2

• i = 2: total = -2 → start = 3

• i = 3: total = 3

• i = 4: total = 3 + (5 - 2) = 6
  Return start = 3

Conclusion

This problem is an excellent example of a greedy strategy combined with a feasibility check. Once it's confirmed that a complete loop is possible, identifying the correct starting point is simply a matter of restarting when the tank balance drops below zero.