Gas Station | Practice Medium 0 attempts
GeeksforGeeks ↗

Gas Station | Practice

Medium Stack&Queue GeeksforGeeks

Imagine n gas stations arranged around a circular route, where station i provides gas[i] units of fuel and it takes cost[i] fuel to drive from station i onward to the next one. Starting your trip with an empty tank, find a starting station from which you could complete the full loop in one direction; if there's no such station, return -1. You can assume that whenever a valid starting point exists, it is the only one.

Input Format
Implement gasStation(gas, cost). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
Output
3

Example 2

Input
gas = [2,3,4]
cost = [3,4,3]
Output
-1
Constraints
  • 1 <= N <= 10^5
  • 0 <= gas[i], cost[i] <= 10^4
Test Cases (2)
Case 1
Args: [[1,2,3,4,5],[3,4,5,1,2]] Expected: 3
Case 2
Args: [[2,3,4],[3,4,3]] Expected: -1
Topics
Stack&Queue

Approach: Greedy

If total gas >= total cost, a solution exists. Track the current tank as you traverse. Whenever the tank goes negative, the start must be after the current station. Reset start to the next station and reset current tank.

javascript
function gasStation(gas, cost) {
  let totalTank = 0, currTank = 0, start = 0;
  for (let i = 0; i < gas.length; i++) {
    const diff = gas[i] - cost[i];
    totalTank += diff;
    currTank += diff;
    if (currTank < 0) { start = i + 1; currTank = 0; }
  }
  return totalTank >= 0 ? start : -1;
}

Time Complexity: O(n)

Space Complexity: O(1)

Saved in this browser only. Private to you.

JavaScript