Greedy crash course ↗ · 83

134. Gas Station

You drive a circular route of n gas stations. If the total gas covers the total cost, a unique valid starting station is guaranteed. One greedy pass finds it: reset the start candidate to i+1 every time the running tank dips negative.

● MediumGreedyPrefix SumSingle PassTypeScript

PROBLEM What we're solving

You are given two arrays gas and cost of length n. You drive a car in a circle: starting at station i you collect gas[i] litres and spend cost[i] to reach station (i+1)%n. Return the index of the starting station that lets you complete the full loop, or -1 if none exists. The answer is guaranteed unique if it exists.

Worked example. gas=[1,2,3,4,5], cost=[3,4,5,1,2]. The net gains are [-2,-2,-2,3,3]. Starting at station 3: tank goes 3→6→4→2→0 — never negative. Answer: 3.

KEY IDEA Total feasibility + greedy start reset

Insight → if sum(gas) ≥ sum(cost) then a valid start is guaranteed to exist and is unique. To find it, scan left to right tracking a running currentTank. The moment it goes negative, every station from the original start up through i is disqualified (they all accumulate the same deficit). Reset start = i+1 and currentTank = 0. Whatever is left after the full scan is the answer — no second pass needed.

RECIPE One-pass greedy scan

0 · Initialise. Set totalTank=0, currentTank=0, start=0. The first two track overall feasibility and local viability; the last tracks the current candidate.
1 · Accumulate net gain. At each station i, compute net = gas[i] - cost[i] and add it to both tanks. The total tank keeps the global sum; the current tank tests the run from start.
2 · Reset on negative current tank. If currentTank < 0, set start = i + 1 and reset currentTank = 0. Any station in the discarded range would carry the same deficit forward — none of them can be the answer.
3 · Decide. After the loop, return start if totalTank ≥ 0, else -1. The global check catches infeasibility; the local scan found the unique valid start.

Classic confusion → why does resetting to i+1 skip intermediate stations safely? Because if starting at j (for any j between the old start and i) already accumulates a smaller prefix than starting at start, it would run out even sooner. The deficit at i proves every station in [start, i] fails — not just start.

COST Complexity & alternatives

Try every start (brute force)

O(n²)

Simulate the loop from each of the n stations.

Greedy single pass

O(n)

One pass, O(1) space — handles both feasibility and start in one loop.

The greedy approach works because the problem guarantees at most one valid start; that uniqueness is what lets us commit to i+1 without backtracking. Space is O(1) — just three scalars.

Pattern transfer →the “reset start on deficit” move appears in Kadane's algorithm (reset the running sum when it goes negative), Jump Game (extend reach greedily), and circular-array problems like Circular Queue and Task Scheduler. Whenever a local sum going negative kills an entire prefix of candidates, this greedy reset pattern applies.

RUN IT Reset start whenever the tank goes negative

gas =cost =

step 0 / 6

STARTInput: gas=[1,2,3,4,5], cost=[3,4,5,1,2]. Net gain at each station = gas[i]-cost[i]. Initialise totalTank=0, currentTank=0, start=0.

1function canCompleteCircuit(gas: number[], cost: number[]): number {
2▶  let totalTank = 0;
3▶  let currentTank = 0;
4▶  let start = 0;
5 
6  for (let i = 0; i < gas.length; i++) {
7    const net = gas[i] - cost[i];
8    totalTank += net;
9    currentTank += net;
10 
11    // Can't reach the next station from the current start candidate.
12    // Any start in [start, i] is ruled out — reset to i+1.
13    if (currentTank < 0) {
14      start = i + 1;
15      currentTank = 0;
16    }
17  }
18 
19  // If total gas < total cost, the circuit is impossible.
20  return totalTank >= 0 ? start : -1;
21}

net[i] = gas[i]−cost[i]-20-21-223334

State

totalTank

tank

start

—

net

current station icurrent start candidateconfirmed answernegative tank / fail

slowfast

TYPESCRIPT The solution, annotated

canCompleteCircuit.ts
function canCompleteCircuit(gas: number[], cost: number[]): number {
  let totalTank = 0;
  let currentTank = 0;
  let start = 0;

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

    // Can't reach the next station from the current start candidate.
    // Any start in [start, i] is ruled out — reset to i+1.
    if (currentTank < 0) {
      start = i + 1;
      currentTank = 0;
    }
  }

  // If total gas < total cost, the circuit is impossible.
  return totalTank >= 0 ? start : -1;
}

Reading it block by block

Lines 2–4 — initialise three scalars. totalTank will hold the running sum of all net gains (used only for the feasibility check at the end). currentTank tracks gas remaining since the last reset of start. start is the current best candidate for the answer.

Lines 6–9 — accumulate net gain at each station. net = gas[i] - cost[i] is the station's contribution. Adding it to both tanks is the key move: the total keeps the global picture; the current tank tests the run from start.

Lines 12–15 — reset when the current tank goes negative. A negative currentTank means we can't reach station i+1 from start. More importantly, any intermediate station would also fail (proven by the prefix argument). So we jump start to i+1 and clear the running tank.

Line 19 — feasibility guard. If totalTank < 0, total gas is insufficient globally; no start works. Otherwise the unique valid start is exactly start— the last index we didn't have to abandon.

Complexity → O(n) time — a single loop over n stations. O(1) space — only three integer variables regardless of input size.

INTERVIEWFollow-ups they'll ask

“Prove the greedy skip is safe.” If starting at start fails at i, any j ∈ (start, i] begins with a partial prefix that is strictly smaller (it misses the positive contribution of earlier stations) — so it also fails at or before i.
“What if there are multiple valid starts?”The problem guarantees uniqueness, but if the constraint were relaxed you'd need a different approach — possibly collecting all prefix-sum positions where the running min is achieved.
“Can you do it in two passes?” Yes — first check total gas vs total cost, then find the station where the cumulative sum is globally minimum; the answer is the index right after that. Same O(n) time, arguably less intuitive.
“What if gas/cost are floats?” The algorithm is identical; just be careful about floating-point equality when checking totalTank ≥ 0 — use a small epsilon tolerance.
“How does this relate to Kadane's?”Both reset a running sum to zero when it goes negative. Kadane finds the max-sum subarray; Gas Station finds the start of the “best wrap-around subarray” that clears zero. The greedy insight is identical.

OPTIMAL Greedy

canCompleteCircuit.ts
function canCompleteCircuit(gas: number[], cost: number[]): number {
  let totalTank = 0;
  let currentTank = 0;
  let start = 0;

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

    // Can't reach the next station from the current start candidate.
    // Any start in [start, i] is ruled out — reset to i+1.
    if (currentTank < 0) {
      start = i + 1;
      currentTank = 0;
    }
  }

  // If total gas < total cost, the circuit is impossible.
  return totalTank >= 0 ? start : -1;
}

Complexity → O(n) time — a single loop over n stations. O(1) space — only three integer variables regardless of input size.

ALT 1 Brute force — simulate from every start

O(n²) time · O(1) space

Try each station as the start and simulate the full circular loop; the first start whose tank never dips below zero is the answer. The literal "just try them all" baseline.

approach-2.ts
function canCompleteCircuit(gas: number[], cost: number[]): number {
  const n = gas.length;

  for (let start = 0; start < n; start++) {
    let tank = 0;
    let ok = true;
    // Drive the whole circle, visiting all n stations wrapping around.
    for (let step = 0; step < n; step++) {
      const i = (start + step) % n;
      tank += gas[i] - cost[i];
      if (tank < 0) { ok = false; break; } // can't reach the next station
    }
    if (ok) return start;
  }
  return -1;
}

Note → Each candidate start replays the entire loop, so it is O(n²) and times out on long routes. The greedy pass uses the fact that a deficit at i rules out every start in [start, i] at once, so a single O(n) scan suffices.

MNEMONIC The one-liner

"If the tank runs dry, every station behind you is to blame — skip to the next one."

TRIGGERS When you see _ → reach for _

circular route, choose a start index	greedy start reset
running sum goes negative → discard prefix	Kadane / gas-station reset
total sum feasibility check + single-pass find	totalTank + currentTank pattern
"complete the circuit" or "lap the array"	greedy reset to i+1

SKELETON The reusable shape

skeleton.ts
function canCompleteCircuit(gas: number[], cost: number[]): number {
  let totalTank = 0;
  let currentTank = 0;
  let start = 0;

  for (let i = 0; i < gas.length; i++) {
    const net = gas[i] - cost[i];
    totalTank += net;
    currentTank += net;
    if (currentTank < 0) {
      start = i + 1;
      currentTank = 0;
    }
  }

  return totalTank >= 0 ? start : -1;
}

FLASHCARDS Tap to flip

What is the greedy key insight?

If sum(gas) ≥ sum(cost) a valid start exists and is unique. Find it by resetting start = i+1 whenever currentTank goes negative.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time complexity of the greedy single-pass solution?

QUESTION 02

gas=[1,2,3,4,5], cost=[3,4,5,1,2]. What does the algorithm return?

QUESTION 03

When the running currentTank goes negative at index i, why do we reset start to i+1 and not to start+1?

QUESTION 04

gas=[2,3,4], cost=[3,4,3]. What does the algorithm return?

QUESTION 05

What is the space complexity of the greedy solution?

QUESTION 06

Which classic algorithm shares the same "reset running sum to zero when it goes negative" insight as Gas Station?

QUESTION 07

If the problem allowed multiple valid starting stations instead of exactly one, what would break in this algorithm?

QUESTION 08

#134 · Gas StationIf total gas ≥ total cost a unique starting station exists. Sweep the circuit, resetting the start to i+1 whenever the running tank goes negative; the last reset is the answer.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Total feasibility + greedy start reset

RECIPE One-pass greedy scan

COST Complexity & alternatives

RUN IT Reset start whenever the tank goes negative

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Greedy

ALT 1 Brute force — simulate from every start

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _