Problem Statement

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

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

Additional information

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

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.

Brute Force (Simulation)

Intuition

The most direct way to solve this is to simply try every single gas station as a starting point.

For each station i, we simulate the journey around the circular track. We keep a running total of the gas in our tank. If at any point the tank drops below 0, we know that starting at station i is a failure. We then break out of the simulation and try starting at station i + 1. If our simulation successfully completes a full loop (n stations visited) without the tank dropping below 0, we have found our answer!

To handle the circular nature of the track, we use the modulo operator % len(gas) to loop back to index 0 when we go past the end of the array.

Algorithm

1. Store the number of stations n.
2. Loop start from 0 to n - 1. This represents the station we are currently testing as our starting point.
3. Initialize tank = 0 and a boolean flag possible = True.
4. Loop step from 0 to n - 1 to simulate the n steps of the journey.
5. Calculate the current station index using modulo: station = (start + step) % n.
6. Add the gas gained and subtract the gas spent: tank += gas[station] - cost[station].
7. If tank < 0, set possible = False and break out of the inner loop (this starting point failed).
8. If the inner loop finishes and possible is still True, return start.
9. If the outer loop finishes without returning, return -1.

def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    n = len(gas)
    
    for start in range(n):
        tank = 0
        possible = True
        
        for step in range(n):
            station = (start + step) % n
            tank += gas[station] - cost[station]
            
            # If we run out of gas, this start point is invalid
            if tank < 0:
                possible = False
                break
                
        if possible:
            return start
            
    return -1

Time & Space Complexity

• Time complexity: O(N^2)

• Reason: In the worst-case scenario, we might simulate almost the entire journey for every single starting station before failing, leading to nested loops that both run N times.

• Space complexity: O(1)

• Reason: We only use a few integer variables (tank, start, step), taking up constant auxiliary space.

Greedy Algorithm - Optimal

Intuition

We can optimize this to a single O(N) pass using two brilliant mathematical insights:

1. The Global Check: If the total amount of gas we collect across all stations is less than the total cost to travel across all stations, completing the circuit is mathematically impossible. If sum(gas) < sum(cost), we can immediately return -1.
2. The Local Check (The Greedy Jump): If we know a solution exists (because of rule 1), there is a unique starting point. Imagine we start at station A and successfully reach station B, but we run out of gas trying to reach station C.
   Could a station between A and B be a better starting point? No! Since we started at A and accumulated gas up to B, any station between A and B would start with an empty tank, making it even less likely to reach C. Therefore, if we fail at B, every station from A to B is a guaranteed failure. We can confidently skip all of them and try B + 1 as our new starting point!

Algorithm

1. Check the global condition: If sum(gas) < sum(cost), return -1.
2. Initialize current_tank = 0 to track the gas for our current simulated run.
3. Initialize start_index = 0 as our prospective starting station.
4. Iterate i from 0 to len(gas) - 1.
5. Update our tank with the net gas at the current station: current_tank += gas[i] - cost[i].
6. If current_tank < 0:

• Our current starting point (and everything we've visited so far) has failed.
• Set the new potential starting point to the very next station: start_index = i + 1.
• Reset current_tank = 0 for the new journey.

7. Return start_index. (Because of our global check in Step 1, we are guaranteed that this start_index will successfully complete the loop).

def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    # Global check: if total cost exceeds total gas, it's impossible
    if sum(gas) < sum(cost):
        return -1
        
    current_tank = 0
    start_index = 0
    
    for i in range(len(gas)):
        current_tank += gas[i] - cost[i]
        
        # If we run out of gas, the current start_index (and all stations up to i) is invalid
        if current_tank < 0:
            start_index = i + 1
            current_tank = 0
            
    return start_index

Time & Space Complexity

• Time complexity: O(N)

• Reason: We compute the sums of the arrays in O(N) time, and then we do a single pass through the array, which also takes O(N) time. The overall time complexity is linear.

• Space complexity: O(1)

• Reason: We only use a few integer variables to track the state, keeping the space complexity constant.