Gas Station | Practice | Problems

There are n gas stations along a circular route. Station i has gas[i] units of fuel and it costs cost[i] to travel from station i to the next station. Starting with an empty tank, return the index of the starting gas station if you can complete the entire circuit once clockwise. If no solution exists, return -1. The answer is guaranteed to be unique if it exists.

Example 1:

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

Sample Input

—

Sample Output

—

Constraints

1 <= N <= 10^5
0 <= gas[i], cost[i] <= 10^4

Test Cases

Case 1

Args: [[1,2,3,4,5],[3,4,5,1,2]] Expected: 3

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.

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.