Pattern 22: LeetCode Interview Patterns24 sections · 736 units
Open in Course

LeetCode 134 Gas Station - Problem Statement

The problem

There are n gas stations in a circle. Station i has gas[i] fuel, and it costs cost[i] to travel to the next station.

Find the starting station index to complete the circuit. Return −1-1 if impossible.

With gas = [1,2,3,4,5], cost = [3,4,5,1,2]:

  • Start at station 3. Tank: 0 + 4 = 4. Cost to next: 1. Tank: 3.
  • Station 4: Tank: 3 + 5 = 8. Cost: 2. Tank: 6.
  • Station 0: Tank: 6 + 1 = 7. Cost: 3. Tank: 4.
  • ... Continue around. Possible!
  • Answer: 33.

Constraints: 1≤n≤1051 \le n \le 10^5. Exactly one solution exists if answer is not −1-1.