Faangprep Logo
LoginRegister
Browse Curriculum
FAANGPrep Sprint
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:

  1. Feasibility Check: If sum(gas) < sum(cost), it's impossible. Return -1.
  2. 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...

1x

Visualize the tank balance. If the running balance drops below zero, we know the starting point must be further ahead.

Previous Problem
Jump Game
Next Problem
Implement Trie (Prefix Tree)

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.