medium

Gas Station

Find the starting gas station that lets you complete a full circuit without running out of fuel.

1. Define the problem

Gas Station

There are n gas stations along a circular route. gasi is the fuel available at station i, and costi is the fuel needed to travel from station i to station i + 1. Return the starting station index that lets you complete the entire circuit once, in the direction of travel, without running out of fuel — or -1 if none exists (the answer is unique if it exists). Use a greedy single pass: whenever the running tank goes negative, the starting point can't be any station up to and including that one — restart the attempt from the very next station.

Constraints

  • n == gas.length == cost.length
  • 1 ≤ n ≤ 105
  • 0 ≤ gasi, costi ≤ 104

Example

Inputgas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output3

Explanation Starting at station 3, the tank never goes negative while completing the full circuit back to station 3.

2. Know the words first

In plain terms

Circuit
A route that returns to its own starting point — station n-1 connects back around to station 0.
3. Visualize the solution

Reset the start whenever the tank goes negative

Reset the start whenever the tank goes negative
Statustank=-2

Station 0: gas−cost = 1−3 = −2. The tank goes negative, so start moves to station 1.

What happens in this step

i = 0: gas[0] − cost[0] = 1 − 3 = −2
totalTank = 0 + (−2) = −2
currentTank = 0 + (−2) = −2

currentTank drops below 0, so station 0 cannot be the start. Reset: start = 1, currentTank = 0.
Step 1 of 5

Steps to visualize

  1. At each station, compute diff = gasi - costi and add it to both the running tank and the total tank.
  2. If the running tank ever drops below zero, no station up to here can be the start — reset it to zero and set start to the next station.
  3. Keep sweeping through every station once.
  4. If the total tank is non-negative at the end, the last reset start is a valid answer; otherwise return -1.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Reset the start whenever the tank goes negative
Statustank=-2

Station 0: gas−cost = 1−3 = −2. The tank goes negative, so start moves to station 1.

What happens in this step

i = 0: gas[0] − cost[0] = 1 − 3 = −2
totalTank = 0 + (−2) = −2
currentTank = 0 + (−2) = −2

currentTank drops below 0, so station 0 cannot be the start. Reset: start = 1, currentTank = 0.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function canCompleteCircuit(gas, cost) {
  let totalTank = 0;
  let currentTank = 0;
  let start = 0;

  for (let i = 0; i < gas.length; i++) {
    const diff = gas[i] - cost[i];
    totalTank += diff;
    currentTank += diff;

    if (currentTank < 0) {
      start = i + 1;
      currentTank = 0;
    }
  }

  return totalTank >= 0 ? start : -1;
}
Time
O(n)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]3example from the docstring
gas = [2, 3, 4], cost = [3, 4, 3]-1total gas is less than total cost, no start can work
gas = [5], cost = [4]0smallest valid input, enough gas to cover its own cost
gas = [3], cost = [5]-1smallest valid input, not enough gas to cover its own cost
gas = [1, 1, 1], cost = [1, 1, 1]0gas exactly matches cost everywhere, starting at 0 always works
gas = [5, 1], cost = [4, 2]0tank stays at exactly zero without ever going negative

Keep reading