There are N gas stations along a circular route, where the amount of gas at stationi 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.
Have you met this question in a real interview?
Yes
Example
Given
4
gas stations with gas[i]=[1,1,3,1]
, and thecost[i]=[2,2,1,1]
. The starting gas station's index is 2
.
Note
The solution is guaranteed to be unique.
Challenge
public class Solution {
O(n) time and O(1) extra space
/**
* @param gas: an array of integers
* @param cost: an array of integers
* @return: an integer
*/
public int canCompleteCircuit(int[] gas, int[] cost) {
// write your code here
int count = 0;
int idx = 0;
for(int i = 0; i < gas.length; i++){
count += gas[i] - cost[i];
if(count < 0){
count = 0;
idx = i+1;
}
}
for(int i = 0; i < idx; i++){
count += gas[i] - cost[i];
}
return count >= 0 ? idx : -1;
}
}
No comments:
Post a Comment