MediumNeetCode150ArrayGreedy
Gas Station
Find starting index to complete circular tour.
Examples
Input
gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output
3
Start at index 3.
Constraints
- •
n == gas.length == cost.length - •
1 <= n <= 10^4 - •
0 <= gas[i], cost[i] <= 10^4
Approaches
Try each station.
CodeT: O(n^2) | S: O(1)
Track total and current surplus.
CodeT: O(n) | S: O(1)
def canCompleteCircuit(gas, cost):
total=0; cur=0; start=0
for i in range(len(gas)):
total+=gas[i]-cost[i]
cur+=gas[i]-cost[i]
if cur<0: cur=0; start=i+1
return start if total>=0 else -1Same approach.
CodeT: O(n) | S: O(1)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | Try each station. |
| Greedy Single Pass | O(n) | O(1) | Track total and current surplus. |
| Greedy Optimized | O(n) | O(1) | Same approach. |
Brute Force
T: O(n^2)S: O(1)
Try each station.
Greedy Single Pass
T: O(n)S: O(1)
Track total and current surplus.
Greedy Optimized
T: O(n)S: O(1)
Same approach.
Common Mistakes
Not checking total gas >= total cost
Wrong start index
Off-by-one