# Golang concise O(N) solution

• If we first start from `gas[0]` and failed at `gas[n]` , we can skip retrying to start from `gas[1]``gas[n-1]` th index.
This can be proved like: let's say we can go through from `gas[1]` to `gas[n]` while we failed from `gas[0]` to `gas[n]` , this happens only the cost to `gas[0]` to `gas[1]` is minus...but then we should have failed from `gas[0]` to `gas[1]` at the first trial, which contradicts the fact.

So when we chose the start point, we can ignore the point in the middle between the start and the failed index. We need to just try going through `len(gas)` distance from the start point we chose in this manner.

``````func canCompleteCircuit(gas []int, cost []int) int {
glen := len(gas)
var start, amount int
LOOP:
// loop to set a new start point
for i := 0; i < glen; {
start, amount = i, 0
// loop to check if we can complete a cycle from start to end
for j := 0; j < glen; j++ {
cur := (start + j) % glen
if amount = amount + gas[cur] - cost[cur]; amount < 0 {
if i+j >= glen {
return -1 // all start points failed
}
i += j + 1 // skip the start point
continue LOOP
}
}
return start
}
return -1
}
``````

The worst scenario is all `gas[i] - cost[i] < 0` but even in this case, we can just chose each point as a start index, so still `O(N)` while N is the length of gas.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.