Gas Station — Greedy Circular
Sanjeev SharmaAdvertisement
Problem
Gas stations in a circle with gas[i] and cost[i]. Find starting index to complete circuit, or -1 if impossible.
Approach — Greedy
If total gas >= total cost, a solution exists and is unique. Track current balance; when it goes negative, start from the next station.
Time: O(n) | Space: O(1)
Solutions
Python
class Solution:
def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
total=curr=start=0
for i,(g,c) in enumerate(zip(gas,cost)):
diff=g-c; total+=diff; curr+=diff
if curr<0: start=i+1; curr=0
return start if total>=0 else -1
C++
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost){
int total=0,curr=0,start=0;
for(int i=0;i<gas.size();i++){
int d=gas[i]-cost[i]; total+=d; curr+=d;
if(curr<0){start=i+1;curr=0;}
}
return total>=0?start:-1;
}
};
Complexity
- Time: O(n) | Space: O(1)
Advertisement
