Gas Station

There are n fuel stations on a circular road, numbered 0 to n - 1. At station i you can pick up gas[i] units of fuel, and driving from station i to the next station (i + 1, or back to 0 from the last one) burns cost[i] units.

Your car's tank has no size limit, and it starts empty. You begin at one station, take its fuel, and drive clockwise. Return the index of a starting station from which you can drive all the way around and return to it without the tank ever going below zero, or -1 if no such station exists.

When a valid starting station exists, the inputs guarantee it is the only one.

Look at the net change at each station, diff[i] = gas[i] - cost[i]. Two facts do all the work.

First, the total decides whether any answer exists. If sum(diff) < 0, the loop burns more fuel than there is, so no start works. If it's ≥ 0, some start does.

Second, a failure rules out a whole stretch of starts. Say you start at s and the tank first goes negative after leaving station j. Every station between s and j was reached with a tank of at least zero, so starting at any of them means arriving at j with less fuel than you had, and you'd fail at j too. So you can skip straight to j + 1 as the next candidate. Each station is visited once, and the last candidate standing is the answer.

def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    total = 0
    tank = 0
    start = 0
    for i in range(len(gas)):
        diff = gas[i] - cost[i]
        total += diff
        tank += diff
        if tank < 0:
            start = i + 1
            tank = 0
    return start if total >= 0 else -1

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

The one-pass code is short; the interviewer cares about the two justifications. Say them as claims: "if the total is non-negative a solution exists" and "if I fail at j, nothing between my start and j can work either." Then prove the second in a sentence: each of those stations was reached with a non-negative tank, so starting there only removes fuel.

Start from the O(n²) simulation and point out the wasted work, a failed start that you then retry from its next station, before introducing the skip. It shows the optimization comes from reasoning about the simulation, not from a remembered trick.