/Interview Study Guide/Algorithms & data structures
#158

Gas Station

medium
Open in editor
arraygreedy

There are n gas stations arranged in a circle, numbered 0 to n - 1. You're given two integer arrays gas and cost, both of length n: gas[i] is the amount of gas available at station i, and cost[i] is the amount of gas needed to travel from station i to station i + 1 (the last station wraps around to station 0).

You begin with an empty tank at a station of your choosing. Return the index of the starting station that lets you travel around the entire circuit once in the forward direction without the tank ever going negative, or -1 if no such station exists.

It is guaranteed that if a valid starting station exists, it is unique.

Example

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

Starting at station 3: tank goes 4 -> 4+5-2=7 -> 7+1-3=5 -> 5+2-4=3 -> 3+3-5=1, completing the loop without going negative.

Constraints

  • n == gas.length == cost.length
  • 1 <= n <= 10^5
  • 0 <= gas[i], cost[i] <= 10^4

Intuition

A first pass just tries every station as the starting point: simulate driving the whole circuit from there, and return the first station whose tank never runs dry.

function gasStation(gas, cost) {
  const n = gas.length;
  // Try every station as a candidate start.
  for (let start = 0; start < n; start++) {
    let tank = 0;
    let ok = true;
    // Simulate one full lap starting from this station.
    for (let step = 0; step < n; step++) {
      const i = (start + step) % n; // wrap around the circle
      tank += gas[i] - cost[i];
      if (tank < 0) { // ran dry before completing the lap
        ok = false;
        break;
      }
    }
    if (ok) return start; // completed the full circuit without going negative
  }
  return -1; // no starting station works
}
Brute force — simulate the full circuit from every candidate start: O(n²).

This is O(n²) — for every candidate start we might re-walk almost the whole circuit before it fails or succeeds. Can we do better?

The key observation: if the running tank (the accumulated gas[i] - cost[i] since some candidate start) goes negative at station i, then every station between that candidate and i is disqualified too — each of them would inherit the same shortfall by the time it reached i, or worse. So the instant the tank dips below zero, it's safe to jump the candidate straight past i and reset the tank to zero, without ever re-walking the stations already ruled out. Accumulating a running total and resetting the candidate the moment it turns negative is the same lens the Prefix sum chapter uses to locate the start of a subarray with a target running-sum property — this greedy search is a specialized case of it.

One more piece: a single left-to-right scan (never wrapping back to re-simulate) is also enough to decide overall feasibility. If the total of gas[i] - cost[i] across every station is negative, no start works at all; if it's >= 0, the candidate start still standing at the end of the scan is guaranteed to complete the full circuit — including the stations skipped by earlier resets, whose shortfall is exactly covered by the surplus banked since start.

Walking it through:

gas = [2, 4, 1, 3, 2, 6, 2], cost = [3, 1, 5, 1, 3, 1, 1] — lane shows diff[i] = gas[i] − cost[i]

i↓start↓
-10
31
-42
23
-14
55
16
diff = 2 - 3 = -1; tank = -1 < 0 → reset

Station 0 can't even cover its own leg to station 1. No station up to and including 0 can be a valid start, so bump start to 1 and zero the tank.

-10
i↓start↓
31
-42
23
-14
55
16
diff = 4 - 1 = 3; tank = 0 + 3 = 3

The tank climbs back into positive territory — station 1 looks promising, but the circuit isn't finished yet.

-10
start↓
31
i↓
-42
23
-14
55
16
diff = 1 - 5 = -4; tank = 3 - 4 = -1 < 0 → reset again

A second dip: everything from start = 1 through here runs dry too. The greedy resets a second time — start jumps to 3, tank back to 0. This can happen more than once in a single scan.

-10
31
-42
start↓
23
-14
55
i↓
16
tank: 2 → 1 → 6 → 7 — never negative

From the new start, the tank climbs through stations 3–6 without ever running dry.

-10
31
-42
start↓
23
-14
55
16
wrap: tank 7 → 6 → 9 → 5 — still never negative

Total gas exceeds total cost overall (5 to spare), so continuing past station 6 back through the skipped stations 0–2 never runs the tank dry either — the surplus banked since station 3 covers their shortfall (the loop itself never re-visits these stations; this is the guarantee proven above).

-10
31
-42
start↓
23
-14
55
16
total = 5 ≥ 0 → return start = 3

The circuit closes back at station 3 with gas to spare the whole way around — station 3 is the unique valid start.

Optimization

Greedy one pass

If total gas is less than total cost, no starting station can work, so return -1 immediately. Otherwise a valid, unique starting station is guaranteed to exist.

Walk the stations once, tracking the running tank (gas[i] - cost[i] accumulated) and a candidate start. Whenever the tank dips below zero at station i, none of the stations from the current start through i can be a valid start (each would run out of gas by at least the same point), so advance start to i + 1 and reset the tank to 0. The station survived once the scan finishes is the answer.

O(n) time, O(1) space.

function gasStation(gas, cost) {
  let total = 0; // running gas - cost over the whole circuit, decides feasibility
  let tank = 0; // running gas - cost since the current candidate start
  let start = 0; // current candidate starting station
  for (let i = 0; i < gas.length; i++) {
    const diff = gas[i] - cost[i]; // net gas gained (or lost) driving away from station i
    total += diff;
    tank += diff;
    // Ran dry at i: no station from start..i can work either, so try i + 1 next.
    if (tank < 0) {
      start = i + 1;
      tank = 0; // fresh candidate starts with an empty tank
    }
  }
  // Overall shortfall means no station works; otherwise the surviving start is the answer.
  return total < 0 ? -1 : start;
}

Complexity analysis

Time complexity: O(n). Here's why:

  • The scan visits each of the n stations exactly once.
  • At each station, computing diff, updating total/tank, and possibly resetting start are all O(1) work.

So the whole scan is a single pass — O(n) — instead of the brute force's O(n²) of re-simulating up to n stations from as many as n different candidate starts.

Space complexity: O(1). Here's why:

  • Only total, tank, start, and the loop index i are kept, regardless of the input's length.
  • No per-station table or copy of gas/cost is built.

So the greedy scan uses O(1) auxiliary space beyond the input arrays themselves.

Test cases

Beyond the example above, these are worth thinking through before you submit.

InputExpected outputDescription
gas = [0], cost = [0]0Smallest possible input — gas and cost both zero, breaking even exactly at the only station.
gas = [1,1], cost = [2,2]-1Smallest no-solution case — total gas falls short of total cost, so no start survives.
gas = [2,2,2], cost = [2,2,2]0All-equal gas and cost — every station breaks even, so the tank never dips negative and station 0 already works.
gas = [1,1,5,1,1], cost = [2,2,1,1,1]2Repeated shortfalls at stations 0 and 1 trigger two separate resets before the surplus at station 2 finally holds all the way through.
gas = [4,1,1], cost = [1,1,1]0Gas comfortably covers cost at every station, so no reset ever triggers — station 0 already works.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor