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

## Comments

## Post a Comment