We can use a greedy approach. If the total gas available is less than total cost, it’s impossible, return -1. Otherwise, a valid starting station must exist. We can track the current gas as we iterate. If it drops below 0, it means the current starting point is invalid, and no station before the current station can be a valid starting point either. We reset our starting point to the next station and reset current gas to 0.
// Pseudocode: Try starting from every single station.
// 1. Loop i from 0 to n-1.
// 2. Simulate the journey. If we complete the circle, return i.
// 3. Return -1.
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
for (int i = 0; i < n; i++) {
int total = 0;
bool possible = true;
for (int j = 0; j < n; j++) {
int idx = (i + j) % n;
total += gas[idx] - cost[idx];
if (total < 0) {
possible = false;
break;
}
}
if (possible) {
return i;
}
}
return -1;
}
};// Pseudocode:
// 1. If sum(gas) < sum(cost), return -1.
// 2. Init total = 0, start = 0.
// 3. Loop i from 0 to n-1:
// 4. total += gas[i] - cost[i]
// 5. if total < 0:
// 6. total = 0
// 7. start = i + 1
// 8. Return start.
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int totalGas = 0, totalCost = 0;
for(int g : gas) totalGas += g;
for(int c : cost) totalCost += c;
if (totalGas < totalCost) return -1;
int total = 0;
int start = 0;
for (int i = 0; i < gas.size(); i++) {
total += gas[i] - cost[i];
if (total < 0) {
total = 0;
start = i + 1;
}
}
return start;
}
};Time: O(n) for a single pass (sum also takes O(n)). Space: O(1).
- Disconnected valid sequences. The logic holds because we check the global sum first. If the global sum is >= 0, the last chosen start will successfully complete the loop.
The key insight is that if you can’t reach station B from station A, you also can’t reach station B from any station between A and B. Thus, the next valid start point to try is B+1.