loading

Gas Station — Step-by-Step Visualization

mediumLeetCode #134ArrayGreedy

There are `n` gas stations along a circular route, where the amount of gas at the `i-th` station is `gas[i]`. You have a car with an unlimited gas tank and it costs `cost[i]` of gas to travel from the `i-th` 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.

Algorithm Pattern

Greedy Circular One-Pass

Key Idea

If the total gas is less than the total cost, it's impossible to complete the circuit. Otherwise, we can pick a starting station such that we never run out of gas. If we start at node `S` and find that we can't reach node `K`, then no node between `S` and `K` can be a valid starting point either.

Step-by-Step Approach

  1. Check if `sum(gas) < sum(cost)`. If so, return -1.
  2. Initialize `total_tank = 0`, `current_tank = 0`, and `start_index = 0`.
  3. Iterate through the stations.
  4. Accumulate `current_tank += gas[i] - cost[i]`.
  5. If `current_tank < 0`, reset `current_tank = 0` and set `start_index = i + 1`.
  6. Return `start_index`.

Common Gotchas

  • The 'total gas >= total cost' check ensures a solution exists; the greedy pass finds where it MUST start.

Related Problems

← All problems