Gas Station: Greedy Reset Pattern

Learning Outcome

After this lesson, you should be able to prove why a failed fuel segment cannot contain a valid start.

Problem Statement

Given gas and cost arrays, return the start index that lets you complete the circuit, or -1 if impossible.

Brute Force Approach

Try every station as a start and simulate the full circuit. This costs O(n^2).

Optimized Approach

Track total fuel and a local tank. If the local tank becomes negative at i, no start from the current candidate through i can work, so reset start to i + 1.

Exact Pseudocode

total = 0
tank = 0
start = 0
for i from 0 to n - 1:
  diff = gas[i] - cost[i]
  total += diff
  tank += diff
  if tank < 0:
    start = i + 1
    tank = 0
if total < 0:
  return -1
return start
  

Reference Code

class Solution:
    def canCompleteCircuit(self, gas, cost):
        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 -1 if total < 0 else start
  

Sample Dry Run

Complexity

Edge Cases

• If total gas is less than total cost, return -1.
• The answer is unique in the standard version when one exists.
• Reset start only after local tank becomes negative.

Interview Checklist

• Track total feasibility separately from local tank.
• Reset candidate start to i + 1 on local failure.
• Return -1 when total is negative.

FAQs

If the tank from the candidate start to i is negative, any start inside that segment has even less helpful prefix fuel.

A local candidate can survive, but the whole circuit is impossible if total fuel is negative.

Greedy reset after a failed segment.