Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumgreedy

Gas Station

Problem (restated)

Circular route of gas stations with gas[i] and cost[i]. Return starting index to complete circuit, or -1.

Intuition

If total gas < total cost impossible. Unique start: when tank goes negative, next index is new candidate.

Approaches

Unique circuit start

Unverified

Time O(n)Space O(1)

Idea. Track total and tank; on tank<0 reset start=i+1, tank=0.

Walkthrough. Classic unique start when sum(gas-cost)>=0.

Trade-offs. One pass vs trying every start O(n²).

Solution

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

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

Template connection

Greedy circuit / reset on debt.

Reflection

If total gas is below total cost, the answer is −1. Otherwise exactly one start works.
When tank < 0, the next start is i + 1 and the tank resets to 0. A start inside that failing prefix fails too, so you do not walk backward.
One station answers 0 when its gas is enough. Equal stations that cover the cost also answer 0.