There are *N* gas stations along a circular route, where the amount of gas at station *i* is `gas[i]`

.

You have a car with an unlimited gas tank and it costs `cost[i]`

of gas to travel from station *i* to its next station (*i*+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

**Note:**

The solution is guaranteed to be unique.

**Java**

Time complexity: O(N)

Space complexity: O(1)

public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { if (gas == null || gas.length == 0){ return -1; } int start = 0; int fuel = 0; int tank = 0; for (int i = 0; i < gas.length; ++i){ fuel += gas[i] - cost[i]; tank += gas[i] - cost[i]; if (tank < 0){ tank = 0; start = i + 1; } } return fuel >= 0 ? start : -1; } }

**Go**

Time complexity: O(N)

Space complexity: O(1)

func canCompleteCircuit(gas []int, cost []int) int { if gas == nil || len(gas) == 0{ return -1; } var fuel, tank, start int = 0, 0, 0 for i := 0; i < len(gas); i++ { fuel += gas[i] - cost[i] tank += gas[i] - cost[i] if tank < 0{ tank = 0 start = i + 1 } } if fuel < 0{ return -1 } else{ return start; } }

Advertisements