Gas Station [Code + Interactive Visualization]

Array Greedy Medium

Python Java C++

def canCompleteCircuit(gas, cost):
    # Track total diff and current sum starting from potential position
    total = 0
    currSum = 0
    start = 0
    
    # If we can't reach next station, start must be after current position
    for i in range(len(gas)):
        diff = gas[i] - cost[i]
        total += diff
        currSum += diff
        
        if currSum < 0:
            start = i + 1
            currSum = 0
    
    # If total >= 0, we can complete circuit starting from 'start'
    return start if total >= 0 else -1

public class Solution {
    // Tricky but pretty easy to understand once you think about algorithm
    // Remember if sum of gas is greater than sum of all the costs then a solution must exist 
    // Also remeber it is guaranteed to be unique
    public int canCompleteCircuit(int[] gas, int[] cost) {
        
        int total = 0;
        int currSum = 0;
        int start = 0;

        // If we hit a point where we cant get to the next one then set start to next one
        for (int i = 0; i < gas.length; i++) {
            
            int diff = gas[i] - cost[i];
            total += diff;
            currSum += diff;
            
            if (currSum < 0) {
                start = i + 1;
                currSum = 0;
            }
        }
        
        // If TOTAL > 0 then we can defintiley complete the circuit. Important to remember that
        if (total >= 0) {
            return start;
        } else {
            return -1;
        }   
    }
}

class Solution {
public:
    int canCompleteCircuit(vector& gas, vector& cost) {
        // Track total diff and current sum starting from potential position
        int total = 0;
        int currSum = 0;
        int start = 0;
        
        // If we can't reach next station, start must be after current position
        for (int i = 0; i < gas.size(); i++) {
            int diff = gas[i] - cost[i];
            total += diff;
            currSum += diff;
            
            if (currSum < 0) {
                start = i + 1;
                currSum = 0;
            }
        }
        
        // If total >= 0, we can complete circuit starting from 'start'
        return total >= 0 ? start : -1;
    }
};

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.

Detailed Explanation

Approach

This solution uses a greedy approach based on two key insights: First, if the total gas is greater than or equal to the total cost, a solution must exist. Second, if we can't reach a station from our current start point, the actual start point must be after our current position.

Key Concepts

1. Total Sum Check: If total gas >= total cost, a valid circuit exists
2. Running Sum: Track available gas as we traverse stations
3. Start Position: If we can't reach next station, start must be moved forward

Algorithm Steps

1. Initialize tracking variables:
   • total: Overall sum of gas-cost differences
   • currSum: Running sum from current start position
   • start: Potential starting position
2. For each station i:
   • Calculate gas[i] - cost[i] difference
   • Add to both total and current sum
   • If currSum becomes negative:
     • Update start to next station
     • Reset currSum to 0
3. Return start if total >= 0, else return -1

Interactive Visualization

Previous Step Next Step Reset

Current Position

0

Start Position

0

Current Sum

0

Total

0

Click "Next Step" to begin the visualization

Time and Space Complexity

• Time Complexity: O(n) - Single pass through the arrays
• Space Complexity: O(1) - Only using a few variables