hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Gas Station

  • Problem: 134. Gas Station

  • Problem Link: leetcode.com/problems/gas-station/

  • Companies Asked: IBM, Uber, Apple, Adobe, Amazon, Tiktok, Microsoft, Bloomberg, Walmart Global Tech


  • Approach:

    1. The basic intuition of the solution is - if there is any situation where the current amount of gas went to the negative, then all the previous gas stations are not off any work.

    2. So just leave them and move forward with the next gas station.

    3. Traverse through the given gas stations and the cost of having gas for the next stations.

    4. Calculate the total amount of gas and the total amount of costs.

    5. Calculate the current amount of gas, current_gas = current_gas + (gas[i] - cost[i])

    6. Now if current_gas becomes less than 0, reset the current_gas and start moving from, i + 1, this could be our answer if we can move toward the end.

    7. Once we reach the end if total_gas is less than total_cost then return -1. That is the only criterion to return -1.

    8. If we have enough total_gas to accommodate the total_cost then return the answer.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(1)


Code [C++]

class Solution {

public:

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

int n = gas.size(), current_gas = 0;

int total_gas = 0, total_cost = 0, start = 0;


for(int i=0; i<n; i++){

total_gas += gas[i];

total_cost += cost[i];


current_gas += (gas[i] - cost[i]);

if(current_gas < 0){

start = i + 1; current_gas= 0;

}

}

if(total_gas < total_cost) return -1;

return start;

}

};