Solution: Gas Station

Let's solve the Gas Station problem using the Greedy Techniques pattern.

We'll cover the following

Statement

There are nn gas stations along a circular route, where the amount of gas at the ithi^{th} station is gas[i].

We have a car with an unlimited gas tank, and it costs cost[i] of gas to travel from the ithi^{th} station to the next (i+1)th(i+1)^{th} station. We begin the journey with an empty tank at one of the gas stations.

Find the index of the gas station in the integer array gas such that if we start from that index we may return to the same index by traversing through all the elements, collecting gas[i] and consuming cost[i].

  • If it is not possible, return -1.

  • If there exists such index, it is guaranteed to be unique.

Constraints:

  • gas.length ==== cost.length
  • 1 ≤\leq gas.length, cost.length ≤103\leq 10^3
  • 0 ≤\leq gas[i], cost[i] ≤103\leq 10^3

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach would be to choose each station as a starting point in the outer loop and try to visit every other station while maintaining the current gas level in the inner loop. This will check for every gas station to be the starting gas station from where we can complete a round trip clockwise.

The time complexity of the naive approach would be O(n2)O(n^2), since we are using a nested loop.

Optimized approach using the greedy pattern

The greedy approach is to keep track of the amount of gas in the tank and the total cost of the journey. If we find that we cannot complete the journey starting from the current gas station, we reset the starting point to the next gas station and continue from there. This means we are making locally optimal choices at each step to find a solution. Therefore, this approach is considered a greedy algorithm.

The logic of the above algorithm is given below:

  1. If the total cost of the journey is greater than the total amount of gas available at all the gas stations, then it is impossible to travel through all gas stations, so the function returns −1-1.

  2. We will iterate through the gas stations from the start. While iterating these stations, we will perform the steps below:

    • At each gas station, we will calculate the amount of current gas available. We’ll do this by subtracting the cost of the journey from the gas available at that station and adding it to the current gas available.

    • If the amount of currently available gas at any station becomes negative, we cannot travel further from the current station. Therefore, we reset the currentGas variable to 00 and start from the next gas station.

  3. Return the index of the gas station from where we can start our journey in such a way that we can travel through all gas stations and reach the starting gas station again.

The starting index will be the index of that gas station from which we can start our journey in such a way that we can travel through all gas stations and reach the starting gas station again.

Let’s look at the following illustration to get a better understanding of the solution:

Press + to interact
canvasAnimation-image
1 of 13

Let’s implement the algorithm as discussed above:

import java.util.*;
class GasStations {
    public static int gasStationJourney(int[] gas, int[] cost) {
        
        if (Arrays.stream(cost).sum() > Arrays.stream(gas).sum()) {
            return -1;
        }
        int currentGas = 0;
        int startingIndex = 0;
        for (int i = 0; i < gas.length; i++) {
            currentGas += gas[i] - cost[i];
            if (currentGas < 0) {
                currentGas = 0;
                startingIndex = i + 1;
            }
        }
        return startingIndex;
    }
    // Driver code
    public static void main(String[] args) {
        int[][] gas = {
            {1, 2, 3, 4, 5},
            {2, 3, 4},
            {1, 1, 1, 1, 1},
            {1, 1, 1, 1, 10},
            {1, 1, 1, 1, 1},
            {1, 2, 3, 4, 5}
        };
        int[][] cost = {
            {3, 4, 5, 1, 2},
            {3, 4, 5},
            {1, 2, 3, 4, 5},
            {2, 2, 1, 3, 1},
            {1, 0, 1, 2, 3},
            {1, 2, 3, 4, 5}
        };
        for (int i = 0; i < cost.length; i++) {
            System.out.print(i + 1);
            System.out.println(".\tGas: " + Arrays.toString(gas[i]));
            System.out.println("\tCost: " + Arrays.toString(cost[i]));
            System.out.println("\tThe index of the gas station we can start our journey from is "+ gasStationJourney(gas[i], cost[i])+ " (If it's -1, then that means no solution exists)");
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Gas Station

Solution summary

To recap, the solution to this problem can be divided into the following three parts:

  1. If the sum of all values in the gas array is less than the sum of all values in the cost array, we return -1, because there will be no gas station from which we can start our journey to complete the round trip.

  2. Traverse the gas list with startingIndex initially set to 0.

    • We calculate currentGas left by incrementing currentGas (initially 0 at the starting point) to (gas[i] - cost[i]).

    • If at any point, our currentGas is less than 0, it means we can not start from this index. Therefore, we increment startingIndex to i+1 and reset currentGas to 0.

  3. Return startingIndex at the end of the traversal.

Time complexity

The time complexity is O(n)O(n), since there are nn elements in the array and we only visit each element once.

Space complexity

The space complexity is O(1)O(1), since we don’t use any additional data structures.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.