Gas Station

Difficulty: Medium Source: NeetCode

Problem

There are n gas stations in a circular route. At station i, you get gas[i] fuel and it costs cost[i] to travel to the next station. You start with an empty tank. Find the starting station index from which you can complete the circuit, or return -1 if no solution exists. The answer is guaranteed to be unique if it exists.

Example 1: Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2] Output: 3

Example 2: Input: gas = [2,3,4], cost = [3,4,3] Output: -1

Constraints:

• 1 <= n <= 10^5
• 0 <= gas[i], cost[i] <= 10^4

Prerequisites

Before attempting this problem, you should be comfortable with:

• Greedy algorithms — key insight about when to abandon a starting position
• Prefix sums — understanding running surplus/deficit

1. Brute Force

Intuition

Try each station as the starting point. Simulate the full circuit from that station. If at any point the tank goes negative, abort and try the next start. If we complete the full loop, return the start index.

Algorithm

1. For each start i from 0 to n-1:
   • Set tank = 0.
   • Simulate going through n stations (wrapping with modulo).
   • If tank goes negative at any point, break.
   • If we complete n steps, return i.
2. Return -1.

Solution

def canCompleteCircuit(gas, cost):
    n = len(gas)

    for start in range(n):
        tank = 0
        can_complete = True
        for step in range(n):
            i = (start + step) % n
            tank += gas[i] - cost[i]
            if tank < 0:
                can_complete = False
                break
        if can_complete:
            return start

    return -1


print(canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))  # 3
print(canCompleteCircuit([2, 3, 4], [3, 4, 3]))               # -1
print(canCompleteCircuit([5], [4]))                            # 0

Complexity

• Time: O(n²)
• Space: O(1)

2. Greedy — Single Pass

Intuition

Two key observations:

1. Feasibility: if sum(gas) < sum(cost), it’s impossible — return -1.
2. Finding the start: if we start from some station and the cumulative surplus (tank) goes negative at station k, then no starting station from the original start up to k can work. Why? Because we already had a positive running sum when passing through those intermediate stations — if they were the start, they’d also fail by station k. So we skip ahead and try k + 1 as the new candidate.

A single pass tracks total_surplus (overall feasibility) and tank (current candidate’s viability).

Algorithm

1. total = 0, tank = 0, start = 0.
2. For each station i:
   • net = gas[i] - cost[i].
   • total += net, tank += net.
   • If tank < 0: reset start = i + 1, tank = 0.
3. If total < 0, return -1.
4. Return start.

Solution

def canCompleteCircuit(gas, cost):
    total = 0
    tank = 0
    start = 0

    for i in range(len(gas)):
        net = gas[i] - cost[i]
        total += net
        tank += net

        if tank < 0:
            # Can't start from 'start' through i; try i+1
            start = i + 1
            tank = 0

    # If overall surplus is negative, it's impossible
    return start if total >= 0 else -1


print(canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))  # 3
print(canCompleteCircuit([2, 3, 4], [3, 4, 3]))               # -1
print(canCompleteCircuit([5], [4]))                            # 0
print(canCompleteCircuit([3, 3, 4], [3, 4, 4]))               # -1
print(canCompleteCircuit([1, 2, 3, 4, 5], [2, 3, 4, 3, 3]))  # 0

Complexity

• Time: O(n)
• Space: O(1)

Common Pitfalls

Not checking total feasibility. The greedy always produces a start candidate, but that candidate is only valid if sum(gas) >= sum(cost). Always check total >= 0 at the end.

Setting start = i instead of start = i + 1. When we fail at station i, station i itself can’t be part of a valid prefix — we start fresh at i + 1.

Resetting total along with tank. Only reset tank when the candidate fails. total accumulates over the whole circuit to check overall feasibility — never reset it.