This visualization was AI-generated. Verify solutions at LeetCode #134
Home → Algorithms → Gas Station

Gas Station

Find the starting gas station index to complete a circular route, or return -1 if impossible.

Greedy LeetCode 134 ↗ Medium

Problem

There are n gas stations along a circular route, where:

  • gas[i] is the amount of gas at station i
  • cost[i] is the cost of gas to travel from station i to station i+1

You have a car with an unlimited gas tank, starting with an empty tank. 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.

Note: If there exists a solution, it is guaranteed to be unique.

Interactive Visualization

Circular Route

Current Station -
Start Candidate 0
Current Surplus 0
Total Surplus 0

Net Gain Per Station (gas[i] - cost[i])

Code 

fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int {    var totalSurplus = 0    var currentSurplus = 0    var start = 0     for (i in gas.indices) {        totalSurplus += gas[i] - cost[i]        currentSurplus += gas[i] - cost[i]         if (currentSurplus < 0) {            start = i + 1            currentSurplus = 0        }    }    return if (totalSurplus >= 0) start else -1}

Status & Log

Explanation

Key Insight

The greedy approach works because:

  • If the total gas is less than the total cost, no solution exists
  • If a solution exists, it's guaranteed to be unique
  • If starting from station A, you can't reach station B (tank goes negative), then any station between A and B also can't reach B (they start with less gas)
  • Therefore, when we fail to reach a station, we can skip all previous stations and try starting from the next one

Algorithm

  1. Track two values: total_surplus (sum of all gas-cost) and current_surplus (current tank level)
  2. Iterate through each station, adding the net gain (gas[i] - cost[i]) to both surpluses
  3. If current_surplus becomes negative, we can't reach the next station from current start:
    • Set start = i + 1 (try next station as starting point)
    • Reset current_surplus = 0
  4. After the loop, if total_surplus >= 0, return start; otherwise return -1

Complexity Analysis

  • Time Complexity: O(n) - single pass through the array
  • Space Complexity: O(1) - only a few variables used