⚡Flashcard Drill➔
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

  1. If the total gas is less than the total cost, no start works -- return -1 immediately.
  2. Otherwise a valid start is guaranteed to exist. Track a running tank balance while scanning.
  3. Whenever the tank goes negative at index i, no start in [start, i] can work, so the next candidate start is i + 1 and the tank resets to 0.
  4. 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 tank but not start: both must move together; the new start is i + 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems