How do you solve the Gas Station problem?

Q: How do you solve the Gas Station problem?

**Target Audience:** Beginners preparing for coding interviews — you should know lists, loops and functions in Python; everything else is explained. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First A ring road has five petrol stations. Your car has an unlimited tank but starts **empty**. At each station you may fill up with whatever that station has, and driving to the next station burns a known amount of fuel. You want to drive all the way round once and come back where you started. Which station should you start from — or is the trip impossible? Start at the w

The problem

Question presented to candidate: "There are n petrol stations on a circular road. Station i has gas[i] units of fuel, and driving from station i to the next one costs cost[i]. Your car starts empty with an unlimited tank. Write a Python function that returns the index of the station to start from to drive around the circle once, or -1 if that is impossible."

What a strong answer should cover:

Reduce each station to its net gain gas[i] - cost[i].
Fact 1: if the total gain is negative, no start works; otherwise one does.
Fact 2: if the tank goes negative after station j, no station from the current start to j can be a start, so jump to j + 1 and reset the tank.
The one-pass solution with total, tank and start: O(n) time, O(1) space — and the prefix-sum argument for why the final start works.
The O(n²) brute force as a baseline, and the % n wrap-around it needs.
Python details: zip(gas, cost) or range(len(gas)), integers that cannot overflow, and that the answer is a station index (not a fuel amount).

Clarifying questions expected:

Does the tank start empty, with no capacity limit?
Is the answer guaranteed to be unique, and what should be returned when there is none?

Code / implementation expected: Yes — can_complete_circuit(gas, cost) in Python 3, one pass.

dsa
greedy
arrays

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you should know lists, loops and functions in Python; everything else is explained.
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

A ring road has five petrol stations. Your car has an unlimited tank but starts empty. At each station you may fill up with whatever that station has, and driving to the next station burns a known amount of fuel. You want to drive all the way round once and come back

The solution is hidden so you can try first

12 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonOne-pass greedy on 7 inputs

Practice

PythonTank trace, 3,000 random cases vs brute force and prefix-min, and work counts