NeetCode #783LC-134MediumGreedyNC 150NC 250
← Back to All Problems#783 · #134 · Gas Station(加油站)
📌 Problem Statement & Constraints
There are
n gas stations in a circle; gas[i] is the fuel available and cost[i] is the fuel to travel to the next station. Starting with an empty tank, return the index of the station to start from to complete the circuit, or -1 if impossible. The answer is unique when it exists. Constraints: 1 <= n <= 10^4, 0 <= gas[i], cost[i] <= 10^4.💡 Core Algorithmic Approaches
- If the total gas is less than the total cost, no start works -- return -1 immediately.
- Otherwise a valid start is guaranteed to exist. Track a running tank balance while scanning.
- Whenever the tank goes negative at index
i, no start in[start, i]can work, so the next candidate start isi + 1and the tank resets to 0. - The insight is that a deficit is a property of the whole prefix, so all prefixes ending at the deficit point can be discarded at once.
💻 Benchmark Python3 Implementation
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
if sum(gas) < sum(cost):
return -1 # impossible regardless of start
start = 0
tank = 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0: # cannot reach i + 1 from start
start = i + 1 # restart after the failure
tank = 0
return start⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass plus the two sums.
💾 Space Complexity
O(1): a few scalars.
⚠️ Interview Pitfalls & Follow-ups
- Skipping the total-gas check: without it, the algorithm would return an invalid start when the circuit is impossible.
- Resetting
tankbut notstart: both must move together; the new start isi + 1. - Simulating from every station: O(n^2) and unnecessary given the prefix argument.
- Assuming the deficit point itself can be the start: the deficit is caused by the prefix ending at
i, so the next candidate is strictly after it.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.