Gas Station medium

Problem Statement

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

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note: If solution is possible, there is only one unique starting gas station.

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 = 3 Travel to station 0. Your tank = 3 + 5 = 8 Travel to station 1. Your tank = 8 - 3 = 5 Travel to station 2. Your tank = 5 + 2 = 7 Travel to station 3. Your tank = 7 - 4 = 3 Travel to station 4. Your tank = 3 + 4 = 7 Travel to station 0. Your tank = 7 - 5 = 2 Travel to station 1. Your tank = 2 + 1 = 3 Travel to station 2. Your tank = 3 - 2 = 1

You can complete the circuit.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3] Output: -1 Explanation: You cannot complete the circuit.

Steps:

1. Calculate the net gain at each station: For each station i, calculate gas[i] - cost[i]. This represents the net gain (or loss) of gas after visiting that station.
2. Find a potential starting point: Iterate through the stations. If the cumulative net gain becomes negative at any point, that starting point is invalid. The reason is if we reach negative gas then there's no way to reach the next gas station. If we get to the last station and totalGas is still nonnegative, the last station can be the starting point. If the cumulative net gain remains non-negative throughout the entire loop, the last station considered is a valid starting point.
3. Check the feasibility: Once a potential starting point is found, verify if a full circuit is possible by starting at that point and simulating the journey.

Explanation:

The key insight is that if a solution exists, there's only one. If the total gas available exceeds the total cost, a solution must exist. This is because if you could never complete the circle, no matter where you started, this would imply that there's a net gas loss, which is false.

We don't need to explicitly simulate the entire journey from each potential starting point. Instead, we keep track of the cumulative net gain (totalGas). If totalGas ever goes negative, we know that the current starting point is invalid and we reset and try a new one. This optimizes the solution to one pass.

Code:

def canCompleteCircuit(gas, cost):
    """
    Finds the starting gas station index to complete a circular route.

    Args:
        gas: A list of gas amounts at each station.
        cost: A list of gas costs to travel to the next station.

    Returns:
        The starting gas station index if possible, otherwise -1.
    """
    n = len(gas)
    total_gas = 0
    total_cost = 0
    start_station = 0
    current_gas = 0

    for i in range(n):
        total_gas += gas[i]
        total_cost += cost[i]
        current_gas += gas[i] - cost[i]
        if current_gas < 0:
            start_station = i + 1
            current_gas = 0

    if total_gas < total_cost:
        return -1  # No solution possible
    else:
        return start_station

Complexity:

• Time Complexity: O(n), where n is the number of gas stations. We iterate through the gas stations at most twice.
• Space Complexity: O(1). We use only a constant amount of extra space.