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

Tested only

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

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?