Problem Description

You have n gas stations arranged in a circle. Each station i has gas[i] amount of gas available. To travel from station i to the next station (i+1), you need cost[i] amount of gas.

You start with an empty gas tank at one of the stations. Your car has an unlimited capacity gas tank, meaning it can hold any amount of gas.

The goal is to determine if there's a starting station from which you can complete one full circle around all stations. If such a starting point exists, return its index. If it's impossible to complete the circuit, return -1.

Key points:

• The route is circular: after station n-1, you return to station 0
• You must visit all stations exactly once in clockwise order
• You start with 0 gas at your chosen starting station
• At each station, you first fill up with all available gas, then spend the required amount to reach the next station
• The problem guarantees that if a solution exists, it will be unique

For example, if gas = [1,2,3,4,5] and cost = [3,4,5,1,2]:

• Starting from station 3: gain 4 gas, spend 1 to reach station 4 → tank has 3
• At station 4: gain 5 gas, spend 2 to reach station 0 → tank has 6
• At station 0: gain 1 gas, spend 3 to reach station 1 → tank has 4
• At station 1: gain 2 gas, spend 4 to reach station 2 → tank has 2
• At station 2: gain 3 gas, spend 5 to reach station 3 → tank has 0
• Successfully completed the circuit, so return 3

Intuition

The key insight is that if the total gas available is less than the total cost needed, it's impossible to complete the circuit regardless of where we start. So sum(gas) >= sum(cost) is a necessary condition.

Now, instead of checking every possible starting point (which would be O(n²)), we can use a clever two-pointer approach that starts from the end of the array and expands in both directions.

The algorithm maintains a window that represents our journey. We start with pointers i and j both at the last station (n-1). The pointer j moves forward (clockwise) to simulate traveling, while pointer i can move backward (counter-clockwise) to include earlier stations as potential starting points.

Here's the brilliant part: when we accumulate gas and find our tank becomes negative (s < 0), instead of starting over from a different position, we expand our window backward by moving i to earlier stations. This is like saying "what if we had started earlier and already had some gas when we reached the problematic segment?"

Think of it this way: if we can't make it from station i to station j with the gas we have, we need to find an earlier starting point that gives us enough initial gas to overcome this deficit. By moving i backward and adding gas[i] - cost[i] to our tank, we're essentially prepending stations to our route.

The algorithm tracks:

• s: the running sum of gas - cost, representing our current tank balance
• cnt: the number of stations we've considered (to ensure we check all n stations exactly once)

If after considering all n stations our tank balance s is still negative, it means the total gas is less than the total cost, making the journey impossible. Otherwise, the position i indicates where we should start to successfully complete the circuit.

This approach is efficient because each station is visited at most once, giving us O(n) time complexity, and we're guaranteed that if a solution exists, this method will find it.

Solution Approach

The implementation uses a two-pointer sliding window technique that starts from the end of the array and expands bidirectionally.

Initialization:

n = len(gas)
i = j = n - 1  # Both pointers start at the last station
cnt = s = 0    # cnt tracks stations visited, s tracks gas balance

Main Algorithm:

The outer while loop continues until we've examined all n stations (cnt < n):

1. Forward Movement (j pointer):

   s += gas[j] - cost[j]  # Add net gas from current station j
   cnt += 1                # Increment station counter
   j = (j + 1) % n        # Move j forward (circularly)

   We first process station j by adding its net gas contribution (gas[j] - cost[j]) to our running sum s. Then we advance j to the next station using modulo arithmetic to handle the circular nature.

2. Backward Expansion (i pointer):

   while s < 0 and cnt < n:
       i -= 1                  # Move starting point backward
       s += gas[i] - cost[i]   # Add gas from new starting station
       cnt += 1                # Increment station counter

   When the gas balance s becomes negative, we can't complete the journey starting from the current i. Instead of resetting, we expand our window backward by decrementing i and including earlier stations. This effectively asks: "What if we had started from an earlier station?"

Example Walkthrough:

Consider gas = [2,3,4] and cost = [3,4,3]:

• Start: i = j = 2, s = 0, cnt = 0
• Step 1: Process station 2: s = 4-3 = 1, cnt = 1, j = 0
• Step 2: Process station 0: s = 1+2-3 = 0, cnt = 2, j = 1
• Step 3: Process station 1: s = 0+3-4 = -1, cnt = 3, j = 2
• Step 4: Since s < 0, move i back: i = 1, s = -1+3-4 = -2, cnt = 4

Since we've examined more than n stations but s is still negative, return -1.

Final Check:

return -1 if s < 0 else i

After processing all stations, if s < 0, the total gas is insufficient for the total cost, so no solution exists. Otherwise, station i is the valid starting point.

Time Complexity: O(n) - each station is visited at most once Space Complexity: O(1) - only using a few variables

Example Walkthrough

Let's walk through a concrete example with gas = [1,2,3,4,5] and cost = [3,4,5,1,2].

Initial Setup:

• n = 5
• i = j = 4 (both pointers start at the last station, index 4)
• s = 0 (gas balance)
• cnt = 0 (stations processed)

Step 1: Process station 4

• Add net gas: s = 0 + (5 - 2) = 3
• Increment counter: cnt = 1
• Move j forward: j = (4 + 1) % 5 = 0
• Since s >= 0, continue forward

Step 2: Process station 0

• Add net gas: s = 3 + (1 - 3) = 1
• Increment counter: cnt = 2
• Move j forward: j = (0 + 1) % 5 = 1
• Since s >= 0, continue forward

Step 3: Process station 1

• Add net gas: s = 1 + (2 - 4) = -1
• Increment counter: cnt = 3
• Move j forward: j = (1 + 1) % 5 = 2
• Now s < 0, so we need to expand backward!

Step 4: Expand backward (inner while loop)

• Move starting point back: i = 4 - 1 = 3
• Add gas from new starting station 3: s = -1 + (4 - 1) = 2
• Increment counter: cnt = 4
• Now s >= 0, exit inner loop

Step 5: Process station 2

• Add net gas: s = 2 + (3 - 5) = 0
• Increment counter: cnt = 5
• Move j forward: j = (2 + 1) % 5 = 3

Final Result:

• We've processed all 5 stations (cnt = 5)
• Final gas balance s = 0 >= 0
• Return starting position i = 3

Verification: Starting from station 3 works!

• Station 3: gain 4, spend 1 → balance = 3
• Station 4: gain 5, spend 2 → balance = 6
• Station 0: gain 1, spend 3 → balance = 4
• Station 1: gain 2, spend 4 → balance = 2
• Station 2: gain 3, spend 5 → balance = 0 ✓

The algorithm efficiently found that station 3 is the correct starting point by expanding the window backward when needed, avoiding the need to check every possible starting position separately.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses two pointers i and j to traverse the gas stations. The key insight is that the variable cnt keeps track of the total number of stations processed. The outer while loop continues as long as cnt < n, and in each iteration (including both the outer loop and inner loop), cnt is incremented by 1. Since cnt starts at 0 and stops when it reaches n, the total number of operations is exactly n. Therefore, each station is visited exactly once, resulting in a linear time complexity of O(n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space regardless of the input size. The variables used are:

• n: stores the length of the input array
• i, j: two pointers for tracking positions
• cnt: counter for the number of stations processed
• s: accumulator for the gas balance

All these variables are simple integers that don't scale with the input size, giving us a constant space complexity of O(1).

Common Pitfalls

1. Incorrect Handling of Negative Index When Moving Backward

The most critical pitfall in this solution is that when we decrement the start_index pointer to move backward, it can become negative. In Python, negative indices have special meaning (they index from the end of the array), but in this algorithm, we need the actual circular previous position.

Problem Code:

while gas_balance < 0 and stations_visited < n:
    start_index -= 1  # This becomes negative!
    gas_balance += gas[start_index] - cost[start_index]  # Wrong index!
    stations_visited += 1

When start_index = 0 and we decrement it, start_index becomes -1. In Python, gas[-1] accesses the last element, which seems correct for circular behavior. However, if we continue decrementing, start_index becomes -2, -3, etc., which doesn't give us the correct circular traversal.

Solution:

while gas_balance < 0 and stations_visited < n:
    start_index = (start_index - 1 + n) % n  # Proper circular decrement
    gas_balance += gas[start_index] - cost[start_index]
    stations_visited += 1

2. Not Validating That We've Actually Completed a Full Circuit

Another pitfall is assuming that if gas_balance >= 0 after visiting n stations, we've found a valid starting point. However, we need to ensure we're actually checking a complete circuit from our starting point.

Enhanced Solution with Validation:

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
      
        # Quick check: if total gas < total cost, impossible
        if sum(gas) < sum(cost):
            return -1
      
        start_index = n - 1
        end_index = n - 1
        stations_visited = 0
        gas_balance = 0
      
        while stations_visited < n:
            gas_balance += gas[end_index] - cost[end_index]
            stations_visited += 1
            end_index = (end_index + 1) % n
          
            while gas_balance < 0 and stations_visited < n:
                start_index = (start_index - 1 + n) % n  # Fixed!
                gas_balance += gas[start_index] - cost[start_index]
                stations_visited += 1
      
        return -1 if gas_balance < 0 else start_index

3. Confusion About What the Algorithm Actually Does

Developers might misunderstand that this algorithm is checking a continuous window of stations rather than simulating a circular journey. The algorithm cleverly finds a starting point by expanding a window backward when needed, effectively checking if there's a contiguous segment of stations whose cumulative gas surplus can cover the entire circuit.

Key Insight: The algorithm works because if the total gas ≥ total cost, there must exist a starting point. By expanding backward when we hit negative balance, we're finding the optimal starting position that maximizes our initial gas accumulation.