Gas Station - Leetcode Solution

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.

1