Skip to main content

134. Gas Station

medium

Find the unique starting gas station that lets you complete a circular tour. A greedy 1D sweep — Kadane-style — beats the O(n^2) brute force.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations. Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

Constraints

  • n == gas.length == cost.length
  • 1 <= n <= 10^5
  • 0 <= gas[i], cost[i] <= 10^4

Examples

Example 1

Input
gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output
3

Explanation: Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4. Travel to station 4. Your tank = 4 - 1 + 5 = 8. Travel to station 0. Your tank = 8 - 2 + 1 = 7. Travel to station 1. Your tank = 7 - 3 + 2 = 6. Travel to station 2. Your tank = 6 - 4 + 3 = 5. Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3. Therefore, return 3 as the starting index.

Example 2

Input
gas = [2,3,4], cost = [3,4,3]
Output
-1

Explanation: You can't start at station 0 or 1, as there is not enough gas to travel to the next station. Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4. Travel to station 0. Your tank = 4 - 3 + 2 = 3. Travel to station 1. Your tank = 3 - 3 + 3 = 3. You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3. Therefore, you can't travel around the circuit once no matter where you start.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If total gas < total cost the journey is impossible — return -1.

Hint 2

If you run out of gas between i and j, no station from i to j can be a valid start.

Hint 3

Restart your candidate at j + 1 and resume the running tank from zero. One pass suffices.

Solution approach

Reveal approach

Two key observations. First, if total(gas) < total(cost), no starting station can complete the tour — return -1. Second, if you start at station i and run out of fuel by the time you try to leave station j (j >= i), then no station in [i, j] can be a valid start, because any later station starts with even less reserve. So restart the candidate at j + 1 and zero the running tank. One pass: maintain total = sum of gas[i] - cost[i] (for feasibility check) and tank = running fuel from current candidate. Whenever tank goes negative after adding gas[i] - cost[i], set candidate = i + 1 and tank = 0. Return candidate if total >= 0 else -1. O(n) time, O(1) space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • greedy
  • kadane
  • prefix-sum

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Gas Station and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →