Greedy Algorithms - Gas Station (Circular)
Given the following code, what is the return value when gas = [2, 3, 4] and cost = [3, 4, 3]?
def canCompleteCircuit(gas, cost):
n = len(gas)
net = [gas[i] - cost[i] for i in range(n)]
if sum(net) < 0:
return -1
prefix = [0] * (2 * n + 1)
for i in range(2 * n):
prefix[i+1] = prefix[i] + net[i % n]
for i in range(n):
if prefix[i+n] - prefix[i] >= 0:
return i
return -1
print(canCompleteCircuit(gas, cost))