# Gas Station
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/gas-station)
Canonical: https://scaleengineer.com/dsa/problems/gas-station
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [BNY Mellon](https://scaleengineer.com/companies/bny-mellon), [Cisco](https://scaleengineer.com/companies/cisco), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Infosys](https://scaleengineer.com/companies/infosys), [Mastercard](https://scaleengineer.com/companies/mastercard), [Oracle](https://scaleengineer.com/companies/oracle), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Yahoo](https://scaleengineer.com/companies/yahoo), [Freecharge](https://scaleengineer.com/companies/freecharge), [Lucid Motors](https://scaleengineer.com/companies/lucid-motors), [PhonePe](https://scaleengineer.com/companies/phonepe), [Zepto](https://scaleengineer.com/companies/zepto), [BitGo](https://scaleengineer.com/companies/bitgo), [Dream11](https://scaleengineer.com/companies/dream11), [CureFit](https://scaleengineer.com/companies/curefit)
---
## 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 + 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**.

**Example 1:**

**Input:** gas = [1,2,3,4,5], cost = [3,4,5,1,2]
**Output:** 3
**Explanation:**
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

**Example 2:**

**Input:** gas = [2,3,4], cost = [3,4,3]
**Output:** -1
**Explanation:**
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

**Constraints:**

* `n == gas.length == cost.length`
* `1 <= n <= 105`
* `0 <= gas[i], cost[i] <= 104`
* The input is generated such that the answer is unique.

# Approaches
## Brute Force Simulation
The most intuitive approach is to try every gas station as a potential starting point. For each starting station, we simulate the entire circular journey to see if it's possible to complete it without the gas tank ever becoming negative.
**Time:** O(N^2) · **Space:** O(1)
**Pros:** Simple to understand and implement.; Correctly solves the problem for all cases.
**Cons:** Inefficient for large inputs due to its quadratic time complexity.
### Explanation
This method iterates through each of the `n` gas stations, considering each one as a potential starting point. For a given starting station `i`, we simulate the journey by moving clockwise around the circuit. We maintain a `tank` variable, which represents the current amount of gas in the car. At each station `j` in the simulated path, we add `gas[j]` and subtract `cost[j]`. If the `tank` ever drops below zero, it means we cannot reach the next station, so this starting point `i` is invalid. We then abandon this simulation and try the next potential starting station `i+1`. If we successfully complete a full circle of `n` stations without the tank becoming negative, we have found our answer, and we return the starting index `i`. If we try all `n` stations as starting points and none of them allow for a complete circuit, it means no solution exists, and we return -1.

```java
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            int tank = 0;
            // We need to check for a full circle, so we check n stations
            for (int j = 0; j < n; j++) {
                int currentStation = (i + j) % n;
                tank += gas[currentStation] - cost[currentStation];
                if (tank < 0) {
                    // This starting point is not possible, break and try the next one
                    break;
                }
            }
            // If the inner loop completed without tank going negative, we found the solution
            if (tank >= 0) {
                return i;
            }
        }
        return -1;
    }
}
```
### Algorithm
*   Loop through each station `i` from `0` to `n-1`.
*   Inside the loop, assume `i` is the starting station. Initialize `tank = 0`.
*   Start a nested loop to simulate the journey for `n` steps.
*   In each step `k`, the current station index will be `j = (i + k) % n`.
*   Update the tank: `tank += gas[j] - cost[j]`.
*   If `tank < 0`, break the inner loop as this starting point `i` is not feasible.
*   If the inner loop completes all `n` steps successfully, it means a full circle was made. Return `i`.
*   If the outer loop finishes without returning, it means no solution was found. Return -1.

## Greedy One-Pass Approach
A more efficient approach leverages a key insight: if the total gas available is less than the total cost to travel, no solution is possible. Conversely, if the total gas is sufficient, a unique solution is guaranteed to exist. We can find this solution in a single pass by keeping track of the current fuel tank level and identifying the correct starting point.
**Time:** O(N) · **Space:** O(1)
**Pros:** Highly efficient with linear time complexity.; Requires constant extra space.; Solves the problem in a single pass.
**Cons:** The logic is less intuitive than the brute-force approach and relies on a greedy proof.
### Explanation
This approach is based on two main observations:

1.  If `sum(gas) < sum(cost)`, it's impossible to complete the circuit. We can check this first. If this condition is met, we can immediately return -1.
2.  If we start at a station `i` and run out of gas before reaching station `j`, it means we cannot start at any station between `i` and `j` either. This is because if we started at any station `k` (where `i <= k < j`), we would have had less fuel when arriving at `j` than if we had started at `i` (since the journey from `i` to `k-1` was possible, meaning the net gas gain was non-negative). Therefore, if we fail at `j`, we must try a starting point after `j`, specifically `j+1`.

We can solve this problem in a single pass. We maintain a `current_tank` variable to track the gas from a potential starting point (`start_station`). We also maintain a `total_tank` to check the overall feasibility.

```java
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int total_tank = 0;
        int current_tank = 0;
        int start_station = 0;

        for (int i = 0; i < n; i++) {
            total_tank += gas[i] - cost[i];
            current_tank += gas[i] - cost[i];

            // If we can't reach the next station from the current start_station
            if (current_tank < 0) {
                // Pick the next station as the new starting point
                start_station = i + 1;
                // Reset the current tank for the new journey
                current_tank = 0;
            }
        }

        // If the total gas is greater than or equal to the total cost, a solution exists.
        // The 'start_station' found is the answer. Otherwise, no solution.
        return total_tank >= 0 ? start_station : -1;
    }
}
```
### Algorithm
*   Initialize `total_tank = 0`, `current_tank = 0`, and `start_station = 0`.
*   Iterate through the stations from `i = 0` to `n-1`.
*   For each station `i`, calculate the net gas change: `gas[i] - cost[i]`.
*   Add this change to both `total_tank` and `current_tank`.
*   If `current_tank` becomes negative, it means we cannot reach station `i+1` from the current `start_station`.
*   Update our potential starting point to be the next station: `start_station = i + 1`.
*   Reset `current_tank` to `0`, as we are starting a new journey attempt from this new `start_station`.
*   After the loop, check if `total_tank` is non-negative. If it is, a solution exists, and `start_station` is the answer. Otherwise, no solution exists.
*   Return `start_station` if `total_tank >= 0`, else return -1.

# Solutions
### CSharp

```csharp
public class Solution {
    public int CanCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.Length;
        int i = n - 1, j = n - 1;
        int s = 0, cnt = 0;
        while (cnt < n) {
            s += gas[j] - cost[j];
            ++cnt;
            j = (j + 1) % n;
            while (s < 0 && cnt < n) {
                --i;
                s += gas[i] - cost[i];
                ++cnt;
            }
        }
        return s < 0 ? -1 : i;
    }
}
```

### Java

```java
class Solution {
public
  int canCompleteCircuit(int[] gas, int[] cost) {
    int n = gas.length;
    int i = n - 1, j = n - 1;
    int cnt = 0, s = 0;
    while (cnt < n) {
      s += gas[j] - cost[j];
      ++cnt;
      j = (j + 1) % n;
      while (s < 0 && cnt < n) {
        --i;
        s += gas[i] - cost[i];
        ++cnt;
      }
    }
    return s < 0 ? -1 : i;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
    int n = gas.size();
    int i = n - 1, j = n - 1;
    int cnt = 0, s = 0;
    while (cnt < n) {
      s += gas[j] - cost[j];
      ++cnt;
      j = (j + 1) % n;
      while (s < 0 && cnt < n) {
        --i;
        s += gas[i] - cost[i];
        ++cnt;
      }
    }
    return s < 0 ? -1 : i;
  }
};

```

### Python

```python
class Solution : def canCompleteCircuit ( self , gas : List [ int ], cost : List [ int ]) -> int : n = len ( gas ) i = j = n - 1 cnt = s = 0 while cnt < n : s += gas [ j ] - cost [ j ] cnt += 1 j = ( j + 1 ) % n while s < 0 and cnt < n : i -= 1 s += gas [ i ] - cost [ i ] cnt += 1 return - 1 if s < 0 else i
```