Medium Difficulty
Gas Station

Array

Greedy

medium

## Gas Station

To solve this problem, we can use the concept of the "circular tour" from the gas station problem. The basic idea is to check if there is a possible starting point that allows us to complete a circular tour without running out of gas.

1. First, we initialize some variables:

• `totalGas`: This variable keeps track of the total gas available after subtracting the total cost of the journey. We initialize it to 0.
• `currentGas`: This variable keeps track of the current gas available as we move from one station to the next. We initialize it to 0.
• `startStation`: This variable stores the index of the potential starting gas station. We initialize it to 0.
2. We iterate through the gas and cost arrays using a loop:

• For each station, we calculate the difference between the gas available (`gas[i]`) and the cost to travel to the next station (`cost[i]`). This difference represents the net gas gain or loss at that station.
• We add this difference to both `totalGas` and `currentGas` variables.
3. Inside the loop, we check if `currentGas` becomes negative:

• If `currentGas` is negative, it means we cannot reach the next station from the current starting station without running out of gas.
• In this case, we reset `currentGas` to 0 and move the `startStation` to the next station (`startStation = i + 1`).
4. After the loop, we check if `totalGas` is negative:

• If `totalGas` is negative, it means the total cost of the journey is greater than the total gas available, and hence, we cannot complete the circular tour no matter where we start.
• In this case, we return -1 to indicate that there is no solution.
5. If we haven't returned -1, it means there exists a solution:

• We return the `startStation` as the index of the gas station from where we can start the journey and complete the circular tour without running out of gas.

The solution uses a greedy approach by continuously updating the starting station whenever `currentGas` becomes negative. By the end of the loop, if there is a solution, the `startStation` will hold the correct index.

``````function canCompleteCircuit(gas, cost) {
const n = gas.length;
let totalGas = 0;
let currentGas = 0;
let startStation = 0;

for (let i = 0; i < n; i++) {
const diff = gas[i] - cost[i];
totalGas += diff;
currentGas += diff;

// If currentGas is negative, we cannot reach the next station.
// So, we reset the currentGas and move the startStation to the next station.
if (currentGas < 0) {
startStation = i + 1;
currentGas = 0;
}
}

// If totalGas is negative, it means the total cost is greater than the total gas available,
// and hence, we cannot complete the circular tour.