Gas Station - LeetCode Solution in C++, Java, Python

1. Introduction

The "Gas Station" problem involves finding a starting point in a circular route of gas stations such that a car, with an unlimited gas tank, can complete the route without running out of gas. This problem tests the ability to use greedy algorithms and understand circular queue concepts.

2. Problem

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 + 1th) 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.

3. Solution in C++

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int total = 0, curr = 0, start = 0;
    for (int i = 0; i < gas.size(); i++) {
        total += gas[i] - cost[i];
        curr += gas[i] - cost[i];
        if (curr < 0) {
            start = i + 1;
            curr = 0;
        }
    }
    return total >= 0 ? start : -1;
}

Explanation:

1. Initialize total and curr to track total and current gas surplus/deficit.

2. Iterate through each station, updating total and curr with the net gas after each station.

3. If curr becomes negative at any point, reset it to 0 and set the next station as the new starting point.

4. After the loop, if total is non-negative, return start; else, return -1 as it's impossible to complete the circuit.

4. Solution in Java

public int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, curr = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        total += gas[i] - cost[i];
        curr += gas[i] - cost[i];
        if (curr < 0) {
            start = i + 1;
            curr = 0;
        }
    }
    return total >= 0 ? start : -1;
}

Explanation:

1. Calculate the total and current balance of gas at each station.

2. If the current balance drops below zero, it means the journey can't be started from the current starting station, so update start.

3. Continue this until all stations are visited.

4. If total gas is non-negative, return start; otherwise, return -1.

5. Solution in Python

def canCompleteCircuit(gas, cost):
    total, curr, start = 0, 0, 0
    for i in range(len(gas)):
        total += gas[i] - cost[i]
        curr += gas[i] - cost[i]
        if curr < 0:
            start = i + 1
            curr = 0
    return start if total >= 0 else -1

Explanation:

1. Traverse each station, calculating the total and curr gas balance.

2. Reset curr to 0 and update start whenever curr becomes negative.

3. After the loop, if total gas is sufficient (non-negative), return start; otherwise, no solution exists, return -1.