What is the Gas Station pattern?

The Gas Station is a common coding interview pattern in Greedy Algorithms problems. It provides a structured approach to solving related algorithm challenges efficiently.

When should I use Gas Station?

Use the Gas Station pattern when you encounter problems matching its characteristics. Check the "When to Use" and "Clues" sections in the lesson for specific indicators.

Is Gas Station asked in FAANG interviews?

Yes, Gas Station is an essential pattern commonly tested in FAANG and top tech company technical interviews.

Greedy Algorithms

Medium

Gas Station

Find the starting gas station to complete the circuit.

10 min read

Solve on LeetCode

Problem Understanding

There are n gas stations along a circular route. gas[i] is the gas at station i. cost[i] is cost to travel to i+1.
Return the index of the starting gas station if you can travel around the circuit once, otherwise return -1. Solution is unique if it exists.

Strategy

Greedy approach:

Feasibility Check: If sum(gas) < sum(cost), it's impossible. Return -1.
Find Start:
- Iterate through stations, accumulating current_tank += gas[i] - cost[i].
- If current_tank < 0, it means we cannot reach station i+1 from our current start. So, the start MUST be after i.
- Reset current_tank = 0 and set start = i + 1.

Interactive Visualization

Step 1 / 1

Initializing...

Custom Input

See the Logic in Motion

Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.

Unlock VisualizerPREMIUM FEATURE

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep