Gas Station

Shreya Deep
Last Updated: May 13, 2022
Difficulty Level :
EASY

Introduction

A circular route is a route in which we move along a circular path and has no endpoints. If there is an array of size n and it is said that it is circular, it means that after reaching the index n-1, we don’t have to stop. We can move further to index 0 from index n-1. Traveling a circular circuit in a clockwise direction means, i.e., if you’re at position i, you can go to position i+1 to move further. Not to the position i-1.  

In this article, we’ll learn how to solve a very famous problem, “Gas station”. 

Problem Statement

The problem states that “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.

Note: In this problem, if there is a solution existing, it is guaranteed to be unique.

For example : 

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 units of gas. 

Your tank = 0 + 4 = 4

Travel to station 4. Tank gas = 4 - 1 + 5 = 8

Travel to station 0. Tank gas = 8 - 2 + 1 = 7

Travel to station 1. Tank gas = 7 - 3 + 2 = 6

Travel to station 2. Tank gas = 6 - 4 + 3 = 5

Travel to station 3. The cost is 5. 

Your gas is just enough to travel back to station 3.

Thus, starting at index 3, you’ll be able to make a complete circular traversal.

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.

 

 If you start at station 2 and fill up with 4 units of gas. 

Tank gas = 0 + 4 = 4.  

Travel to station 0. Tank gas = 4 - 3 + 2 = 3 .

Travel to station 1. Tank gas = 3 - 3 + 3 = 3.

 

You cannot travel back to station 2, as it needs four gas units, but you only have 3. Therefore, you can't travel around the circuit once starting with any of the stations.

 

Before directly jumping to the solution, we suggest you try and solve this problem Gas station on Codestudio.

Brute force approach 

The brute force approach is to iterate through all the stations one by one and check which one can take you to one full circular traversal, i.e., starting from station i, you go through stations i+1,i+2,...0,1,..i. So first we’ll check if we can go to station i+1,i+2,,,n-1? 

If yes, then we’ll check if we can go from station 0 to i. In this way, we’ll be able to make one circular traversal.

The steps are as follows :

  • If the number of stations is 0, return -1 because no solution is possible.
  • Otherwise, iterate through each gas station one by one, from i=0 to i<n. For each i,
    • Declare and initialize a variable gas_cur. It will store the current amount of gas in the tank.
    • Keep a flag, “flag1,” initialized to true. This flag1 will tell if we can reach n-1 starting from this i or not. If we can, the value of flag1 will remain true. Otherwise, it’ll be false. 
    • For checking if we can reach n-1 or not, we’ll run a loop from j=i to j=n-1 and for each j, keep checking if gas_cur<0. Suppose at any j, gas_cur becomes<0; then we can’t move forward. So break out of the loop and update flag1 to false. Otherwise, keep moving ahead until you reach j=n-1. Also, at each j, keep updating the value of gas_cur +=(gas[j]-cost[j]).
    • Now, if we’ve come out of the for loop, and falg1 is false, this i can’t lead to a complete circular traversal, so move on to the next i.
    • If flag1 is still true, this means we can go ahead and check if we can reach from j=0 to j=i with the current gas amount or not. 
    • So now, keep another flag variable, “flag2=true”.This flag2 will tell if we can reach to i with the current amount of gas, from j=0 or not. If we can reach, the value of flag2 will remain true. Otherwise, it’ll be false. 
    • Same as earlier, for checking it, run a loop from j=0 to j=i and for each j, keep checking if gas_cur<0. If at any j, gas_cur becomes<0, then we can’t move forward. So break out of the loop and update flag2 to false. Otherwise, keep moving ahead until you reach j=i. Also, at each j, keep updating the value of gas_cur +=(gas[j]-cost[j]).
    • Now, if we’ve come out of the for loop, and flag2 is false, this i can’t lead to a complete circular traversal, so move on to the next i.
    • If flag2 is still true, it means that we’re able to complete the full circular traversal from i to n-1 and then from 0 to i. So, return the i, and the function will end its execution here. 
    • If after traveling all the i’s, we still don’t get any answer, it means that no solution exists thus return -1.

Implementation

Let’s see the implementation of the above approach.

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int size = gas.size(); 
    if(size == 0) //if there are no stations, return -1.
        return -1;
    for(int i = 0; i < size; i++){
        int gas_cur = 0;
        int gas_cost = 0;
        bool flag1 = true;
        // Check if we can reach n-1 from i or not?
        for(int j = i; j < size; j++){ 
            gas_cur += gas[j];
            gas_cur = gas_cur - cost[j];
            if(gas_cur < 0){
                flag1 = false;
                break;
            }
        }
        if(flag1 == falsecontinue//If no then move on to the next i.
        //Otherwise, check if we can reach i from 0 starting with the current amount of gas in the tank or not?
        bool flag3 = true;
        for(int j = 0; j < i; j++){
            gas_cur += gas[j];
            gas_cur = gas_cur - cost[j];
            if(gas_cur < 0){
                flag3 = false;
                break;
            }
        }
       //If yes, return this i 
        if(flag3 == true
            return i;
        else //Otherwise continue
            continue;
    } 
   //If no suitable i is found and we have traversed the whole array, this means
    //there is no solution. So return -1.
    return -1;
}

Input

n=5,  gas = [1,2,3,4,5], cost = [3,4,5,1,2]

Output

3

 

Complexities

Time Complexity

O(n^2), where n is the number of stations.

Reason: We’re iterating through each i once (which takes O(n) time) and then for each i, we’re searching for the last station where we can reach starting from gas station i (which takes another O(n) time for each i). Therefore, the total time complexity is O(n^2).

Space Complexity

O(1) 

Reason: No extra space is used.

 

Efficient solution

Another approach is there, which is supported by two facts and is very efficient. The facts are: 

  1. If the total number of gas is bigger than the total number of costs. Then only can we find a solution. Otherwise, no solution.
  2. If a car starts at gas station A and can’t reach gas station B, then any gas station between A and B can’t make us reach B. 

 

Proof for 1: For a solution to be existing, we should complete one full circular clockwise traversal of the stations. If the sum of all the number of gases is less than the sum of the number of costs, there will be some gas station x, where cost[x] > gas at x. And therefore, we won’t be able to complete one full circle. 

Proof for 2: Let’s say there is a gas station C between A and B. Now assume we start at A, we’re not able to reach B, but we can reach all the stations till B-1 and C<=B-1. Then when we reach C from A, we must have had some positive gas amount in the tank. Now, if, after starting from this positive amount, we aren’t able to reach B, then how can we reach B after starting from C with gas amount 0? Not possible, right? Thus the fact is true.

Note that here, not being able to reach station B from station A means that at B, gas[B] <cost[B]. 

So based on fact 2, if after starting from A we aren’t able to reach B, we need to initiate our next search from B+1. Therefore, if gas[B]<cost[B], we need to set the total amount of gas in the gas tank as 0 and the start point as B+1. 

The steps are as follows :

  1. Run a for loop and find the total sum of the number of gas at each station. Do the same for finding the sum of the total cost at each station. 
  2. Compare both of these. If total gas<total cost, return -1 because no solution is possible. 
  3. Otherwise, initiate two variables, current_gas, and start_station to 0. 
  4. Run a for loop for iterating through each station, whether we can start from it or not. For any i,  
    1. If the current_gas in the tank at this station becomes negative, we know that i can’t be that start point. So, update the value of current_gas as 0 and start_station as i+1.
    2. Otherwise, keep moving on to the next i. 
  5. Return start_station.

Implementation

Let’s see the implementation of the above approach.

#include<bits/stdc++.h>
using namespace std;

int canCompleteCircuit(vector<int>& gas, vector<int>& cost){
    int total_gas=0;  
    int total_cost=0;
    for(int i = 0;i<gas.size();i++) {  // finding total gas sum and cost sum
        total_gas+=gas[i];
        total_cost+=cost[i];
    }
    if(total_gas<total_cost){ // if total gas sum is less than total cost sum, 
        //there is no solution, so return -1.
        return -1;
    }
    //else 
    // initialize current_gas = 0 and start_station = 0. current_gas denotes the 
    // amount of gas in the tank at the moment. Start_station denotes the index of the 
    // station we're starting with. 
    int current_gas = 0;
    int start_station = 0;
    for(int i = 0;i<gas.size();i++) {
        current_gas += gas[i] - cost[i];
        if(current_gas < 0) { //if current_gas is less than 0, we're not able to reach i from start_station. 
        //So we need to change the start_station to i+1 and current_gas to 0.  
            current_gas= 0;
            start_station = i + 1;
        }
    }
    return start_station; // return start_station. 
}

int main(){
    int n;
    cin>>n;  //total number of gas stations
    vector<int>gas(n); //vector for storing the gas values
    vector<int>cost(n); //vector for storing the cost values
    for(int i=0;i<n;i++){
        cin>>gas[i];
    }
    for(int i=0;i<n;i++){
        cin>>cost[i];
    }
    int ans = canCompleteCircuit(gas,cost);
    cout<<ans<<endl;
  return 0;
}

 

Input

n=5,  gas = [1,2,3,4,5], cost = [3,4,5,1,2]

 

Output

3

 

Complexities

Time Complexity

O(n), where n is the number of gas stations.

Reason: Since we’re just traversing all the stations once, it takes O(n) time. 

Space Complexity

O(1) 

Reason: No extra space is used.  

If you've made it this far, congratulations, Champ. The problem of "Gas station " is now resolved. If you haven't already submitted it to CodeStudio. Without further ado, have it accepted as early as possible.

Attention reader!! In this same problem, a variation can be made by giving distance instead of cost, but the logic will be the same. You can submit the code for this variation here on CodeStudio.

Frequently asked questions

1. What is a circular route?

Answer: A circular route is a route following a path approximating a circle. 

2. Where can I submit my “Gas station” code?

Answer: You can submit your code here on CodeStudio and get it accepted right away.

3. Are there more Data Structures and Algorithms problems in CodeStudio?

Answer: Yes, CodeStudio is a platform that provides both practice coding questions and commonly asked interview questions. The more we’ll practice, the better our chances are of getting into a dream company of ours.

Key Takeaways

In this article, we discussed the gas station problem. Another variation of this problem is here, which has the same logic. We have just replaced the cost vector with a distance vector. So you should try solving it. This was a greedy problem. You’ll find a lot of problems being asked during various coding contests and placements tests from this topic. Some of them are jump gamecontainer with most watercandies, and three ninjas candidate.     

To practice more such problems, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think