algoadvance

There are n gas stations along a circular route, where the amount of gas at the i-th station is represented by gas[i], and the cost to travel from the i-th station to the (i+1)-th station is represented by cost[i].

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

Clarifying Questions

1. Constraints on the input arrays?
   • The arrays gas and cost will have the same non-negative length n, where 1 <= n <= 10^4.
2. Can the gas and cost values be zero?
   • Yes, both gas[i] and cost[i] can be zero.
3. Is the solution always unique if it exists?
   • Yes, if there is a solution, it is guaranteed to be unique.

Strategy

1. Observation:
   • If the total gas available is less than the total cost to travel, it is impossible to complete the circuit.
2. Approach:
   • Calculate the total gas available and the total cost required. If total gas is less than total cost, return -1.
   • Traverse the gas stations while keeping track of the current tank. Start with an empty tank and iterate through each gas station.
   • If at any point the tank becomes negative, reset the starting gas station to the next one.
   • The rationale behind this is that if you can’t get from i to i+1, none of the stations before i can be the starting point.
   • Continue until you find a valid starting point or determine it’s impossible.

Code

def canCompleteCircuit(gas, cost):
    total_gas, total_cost = 0, 0
    tank, start_index = 0, 0
    
    for i in range(len(gas)):
        total_gas += gas[i]
        total_cost += cost[i]
        tank += gas[i] - cost[i]
        
        # If tank is negative, reset the start position
        if tank < 0:
            start_index = i + 1
            tank = 0
    
    # If total gas is less than total cost, it's impossible
    return start_index if total_gas >= total_cost else -1

Time Complexity

The solution works in a single pass through the list, so the time complexity is (O(n)), where (n) is the number of gas stations.

Summary

• We first check if the total gas available is at least as much as the total cost to ensure the trip is feasible.
• Then, we find the starting station by ensuring at any point if we can’t proceed, we reset the starting point.
• This efficiently determines the starting point in linear time.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?