We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Gas Station

Number: 134

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Bloomberg, Meta, Oracle, Salesforce, BitGo, ServiceNow, Microsoft, Freecharge, Cisco, Adobe, Flipkart, TikTok, Apple, Goldman Sachs, PhonePe, EPAM Systems, BNY Mellon

Problem Description

Given two integer arrays gas and cost representing gas stations in a circular route, determine the starting index from which a car (with an unlimited tank but starting empty) can complete the circuit once in a clockwise direction. At each station i, gas[i] is the amount of gas available and cost[i] is the gas required to travel to the next station. If it is not possible to make a complete circuit, return -1.

Key Insights

  • If the total amount of gas available is less than the total travel cost, then completing the circuit is impossible.
  • A greedy approach can be used by keeping track of the current surplus of gas. If the surplus becomes negative at any station, the journey cannot start from any station before that point.
  • Restart the journey from the next station whenever the surplus goes negative.
  • The problem guarantees that if a solution exists, it is unique.

Space and Time Complexity

Time Complexity: O(n), where n is the number of gas stations, as we traverse the list only once. Space Complexity: O(1), as no extra space is used other than a few variables.

Solution

The solution involves iterating over the list of stations while maintaining two variables: one for the current gas surplus and one for the total gas surplus. If at any station the current surplus drops below zero, the current starting station is not viable and we set the starting station to the next index and reset the current surplus. After one pass, if the total gas surplus is non-negative, then the identified station is the valid starting point.

Code Solutions

# Define a function to find starting gas station index
def canCompleteCircuit(gas, cost):
    total_surplus = 0  # Total gas surplus after completing the route
    current_surplus = 0  # Gas surplus while iterating from a candidate start station
    start_index = 0  # Candidate starting station index
    
    # Loop through each station
    for i in range(len(gas)):
        # Calculate net gas after leaving station i
        surplus = gas[i] - cost[i]
        total_surplus += surplus
        current_surplus += surplus
        
        # If current surplus becomes negative, station i is not a valid start.
        if current_surplus < 0:
            # Reset starting station to the next station
            start_index = i + 1
            current_surplus = 0  # Reset current surplus
    # Check if overall surplus is non-negative
    return start_index if total_surplus >= 0 else -1

# Example usage:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
print(canCompleteCircuit(gas, cost))  # Output: 3
← Back to All Questions