Gas Station

Medium

The problem

There are stations in a circle. gas[i] is the fuel you pick up at station i, and cost[i] is the fuel needed to drive from station i to the next one (the last station connects back to station 0). Start with an empty tank at some station and go around once in order. Return the index of the station where you can start and finish the whole circle, or -1 if there is none.

Example 1
Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3
Start at 3. After station 3 you hold 4 - 1 = 3, after 4 you hold 3 + 5 - 2 = 6, after 0 you hold 4, after 1 you hold 2, and after 2 you hold 0. The tank never goes below 0 and you are back at 3.
Example 2
Input: gas = [2, 3, 4], cost = [3, 4, 3]
Output: -1
In total there is 9 gas but 10 is needed, so no start works.

Limits

1 ≤ len(gas) = len(cost) ≤ 100,000
0 ≤ gas[i], cost[i] ≤ 10,000
If an answer exists, it is unique

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

If you cannot get from station A to B, can any station between A and B be a valid start?

The idea

If total gas < total cost return −1. Otherwise scan with a running tank; when it drops below 0 reset it and make the next station the new start.

Target: O(n) time, O(1) space

Go function shape

func canCompleteCircuit(gas []int, cost []int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// CanCompleteCircuit: the start index that completes the circular route, or -1.
// Greedy: if the tank goes negative at i, no start in [start, i] can work, so restart at i+1.
func CanCompleteCircuit(gas, cost []int) int {
	total, tank, start := 0, 0, 0
	for i := range gas {
		diff := gas[i] - cost[i]
		total += diff
		tank += diff
		if tank < 0 {
			start = i + 1
			tank = 0
		}
	}
	if total < 0 {
		return -1
	}
	return start
}

Read the lesson: Greedy