Solution For Gas Station

Problem description:

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.

Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

If there exists a solution, it is guaranteed to be unique.

Both input arrays are non-empty and have the same length.

Each element in the input arrays is a non-negative integer.

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. Travel to station 4. Total cost = 4 + 1 = 5 unit of gas, 5 – 5 = 0. Travel to station 0. Total cost = 5 + 3 = 8 unit of gas, 0 – 1 = -1. Travel to station 1. Total cost = 8 + 4 = 12 unit of gas, 1 – 2 = -1. Travel to station 2. Total cost = 12 + 5 = 17 unit of gas, 2 – 3 = -1. Travel to station 3. Total cost = 17 + 1 = 18 unit of gas, your gas tank has enough gas to travel around the circuit once, so you should return the starting station (index 3).

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]

Output: -1

Explanation:

You can’t start at station 0 or 1, as you wouldn’t have enough gas to travel to the next station.

Let’s discuss the approach to solving the problem:

The idea is based on finding the minimum sum sequence in the circular array. If the total sum of the combined circular array is negative, there is no solution, so return -1.

We can solve the problem in O(n) time complexity by using the following approach:

1. Initialize a count variable to keep track of the total sum of the difference between the gas and cost arrays.

2. Initialize two more variables – start and curr, which will keep track of the starting position and current position respectively.

3. Iterate through the gas and cost arrays, and at each step, update the count variable as:

   count += gas[i] – cost[i]

4. If the count variable is negative, it means that there is no solution, so return -1.

5. If the count variable is positive, it means that there is a solution, so we need to find the starting point.

6. Initialize a variable sum to keep track of the current sum of the difference between the gas and cost arrays.

7. Iterate through the gas and cost arrays again, starting at the first index, and update the sum variable as:

   sum += gas[i] – cost[i]

8. At each step, if the sum variable becomes negative, it means that the current starting position is not valid, so we need to update the starting position to the next index and reset the sum variable.

9. If we reach the end of the array and the sum variable is still positive, it means that the current starting position is valid, so return it as the solution.

Python code solution:

def canCompleteCircuit(gas, cost):

count = 0
sum = 0
start = 0

for i in range(len(gas)):
    count += gas[i] - cost[i]
    sum += gas[i] - cost[i]
    if sum < 0:
        start = i + 1
        sum = 0

if count < 0:
    return -1
else:
    return start

Explanation:

In the above code, we first calculate the sum of the difference between the gas and cost arrays, and if it is negative, we return -1 as there is no solution.

If the count variable is positive, we iterate through the gas and cost arrays again and calculate the sum of their differences. At each step, if the sum becomes negative, we update the starting position to the next index and reset the sum variable.

If we reach the end of the array and the sum variable is still positive, it means that the current starting position is valid, so we return it as the solution.

Time complexity: O(n)

Space complexity: O(1)

Conclusion:

In this article, we discussed the Gas Station problem, which involves finding the starting point in a circular array that allows you to travel around the circuit in a clockwise direction without running out of gas. We saw the efficient approach to solve the problem in O(n) time complexity using Python code.

Step by Step Implementation For Gas Station

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int sumOfGas = 0;
        int sumOfCost = 0;
        int start = 0;
        int tank = 0;
        for (int i = 0; i < n; i++) {
            sumOfGas += gas[i];
            sumOfCost += cost[i];
            tank += gas[i] - cost[i];
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        if (sumOfGas < sumOfCost) {
            return -1;
        } else {
            return start;
        }
    }
}

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # check if there is a valid solution
        if sum(gas) < sum(cost):
            return -1
        
        # keep track of the current and overall gas
        current_gas = 0
        overall_gas = 0
        
        # keep track of the starting index
        start = 0
        
        for i in range(len(gas)):
            current_gas += gas[i] - cost[i]
            overall_gas += gas[i] - cost[i]
            
            # if the current gas is negative, reset the current gas and the start index
            if current_gas < 0:
                current_gas = 0
                start = i+1
        
        return start

There are two solutions for this problem:

1) Find the local minimum gas station and start from there

2) Find the global minimum gas station and start from there

For the first solution, we can keep track of the current gas station and the gas remaining at that station. If the gas remaining is less than 0, then we know that we cannot reach the next station from the current one and we need to start over from the next station. Otherwise, we can keep track of the total gas remaining and continue to the next station.

For the second solution, we can keep track of the global minimum gas station and the gas remaining at that station. If the gas remaining is less than 0, then we know that we cannot reach the next station from the current one and we need to start over from the global minimum station. Otherwise, we can keep track of the total gas remaining and continue to the next station.

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

class Solution {
    public int CanCompleteCircuit(int[] gas, int[] cost) {
        int sumGas = 0;
        int sumCost = 0;
        int start = 0;
        int tank = 0;
        for (int i = 0; i < gas.Length; i++) {
            sumGas += gas[i];
            sumCost += cost[i];
            tank += gas[i] - cost[i];
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        if (sumGas < sumCost) {
            return -1;
        }
        else {
            return start;
        }
    }
}