Course contentsShow
← Computer Science
Lesson 893 of 2,87221. Greedy AlgorithmsFree lesson

Gas Station Circuit Problem

Find starting gas station to complete a circuit by tracking cumulative gas surplus at each station.

Gas Station Circuit Problem

You'll learn how to find the starting gas station that allows you to complete a circular route by tracking cumulative gas surplus.

The Problem Setup

Imagine a circular route with n gas stations. At each station i, you can fill up gas[i] fuel, but traveling to the next station costs cost[i] fuel. The question: Is there a starting station that lets you complete the entire circuit without running out of fuel?

The Greedy Insight

Instead of testing every possible starting point (expensive!), we track a cumulative gas surplus as we simulate traveling around the circuit:

  • At each station, calculate: gas[i] - cost[i] (net gain or loss)
  • Keep a running "tank" total
  • If the tank ever goes negative, you cannot start from any station up to this point
  • The key greedy choice: when you run out of fuel at station j, the next valid candidate starting point must be station j+1

Why? Because if you could reach j from some earlier station k, then starting from k with that accumulated surplus was still not enough. So k (and everything before j) is eliminated.

How It Works

  1. Track two values: current_tank (from current candidate start) and total_surplus (entire circuit)
  2. Traverse all stations once
  3. When current_tank goes negative, reset it and move the candidate start forward
  4. After one pass, check if total_surplus >= 0. If yes, the last candidate works; if no, no solution exists

This works because if the total gas equals or exceeds total cost, exactly one starting point will work, and our greedy elimination finds it.

Key Takeaway: The gas station circuit problem uses a greedy approach by tracking cumulative surplus and resetting the candidate start whenever fuel runs out, solving the problem in a single O(n) pass.