Gas Station

There are n gas stations along a circular route. gas[i] is the fuel you collect at station i; cost[i] is the fuel to travel to the next station. Starting with an empty tank, find the index of the station from which you can complete the full circuit clockwise. Return -1 if it's impossible. At most one valid answer exists.

• 1 ≤ n ≤ 1000
• 0 ≤ gas[i], cost[i] ≤ 1000
• At most one valid starting station

Examples

How to think about it

Define net[i] = gas[i] - cost[i] — the gain or loss at each station. The first key observation: if sum(net) < 0, no starting point works — there simply isn't enough fuel globally. If the total is sufficient, a valid start is guaranteed.

The second observation drives the greedy: if starting from station s you run out of gas at station j, then no station between s and j can be the answer either — each of those intermediate starts would arrive at j with even less fuel. So you can skip the entire range [s, j] and try j+1 next.

Brute Force — O(n²)

Try every station as a starting point. Simulate the full circuit — if the tank ever goes negative, this start fails. If you complete the loop, return it.

def canCompleteCircuit(gas, cost):
    n = len(gas)
    for i in range(n):
        tank = gas[i] - cost[i]
        if tank < 0:
            continue
        j = (i + 1) % n
        while j != i:
            tank += gas[j] - cost[j]
            if tank < 0:
                break
            j = (j + 1) % n
        if j == i:
            return i
    return -1

Each of n starts simulates up to n steps → O(n²). The greedy solution is O(n).

Two Pointers — O(n)

Instead of scanning left-to-right from index 0, place two pointers at opposite ends of the array and squeeze them inward until they meet. The pointer that meets the other is the answer.

Setup

Think of the net array net[i] = gas[i] - cost[i] as a circular sequence. We're looking for a starting index such that all prefix sums of the circular slice are non-negative. The two-pointer trick exploits the fact that there is at most onevalid answer.

• start = n - 1 — right pointer, initialized to the last station
• end = 0 — left pointer, initialized to the first station
• tank = net[start] — running fuel starting from start

How it moves

Each iteration, exactly one pointer moves:

• tank < 0 → the current window starting at start can't sustain itself. Expand left: start--, absorb net[start] into tank. This asks: "can I start one station earlier to gain more fuel?"
• tank ≥ 0 → the current window is self-sustaining so far. Expand right: absorb net[end], then end++. This asks: "can I extend the route to include the next station?"

When start == end, the two pointers have covered the full circle exactly once (they met in the middle). At this point, if tank ≥ 0, startis the answer. Otherwise return -1.

Trace — gas=[1,2,3,4,5], cost=[3,4,5,1,2]

net = [-2, -2, -2, 3, 3]
start=4, end=0,  tank = net[4] = 3    → tank≥0, absorb end=0: tank=3+(-2)=1, end=1
start=4, end=1,  tank = 1             → tank≥0, absorb end=1: tank=1+(-2)=-1, end=2
start=4, end=2,  tank = -1            → tank<0,  move start←: start=3, tank=-1+3=2
start=3, end=2,  tank = 2             → tank≥0, absorb end=2: tank=2+(-2)=0, end=3
start=3, end=3  →  start==end, tank=0≥0  →  return 3 ✓

def canCompleteCircuit(gas, cost):
    n     = len(gas)
    start = n - 1
    end   = 0
    tank  = gas[start] - cost[start]

    while start > end:
        if tank < 0:
            start -= 1
            tank  += gas[start] - cost[start]
        else:
            tank += gas[end] - cost[end]
            end  += 1

    return start if tank >= 0 else -1

Greedy vs Two Pointers — what's the difference?

Greedy — O(n)

One forward pass. Track total (running fuel balance) and res(candidate start). When total drops below zero, everything from the old res to i is ruled out — set res = i + 1and reset total = 0. The global sum check guarantees the final resis valid.

def canCompleteCircuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1

    total = 0
    res   = 0
    for i in range(len(gas)):
        total += gas[i] - cost[i]
        if total < 0:
            total = 0
            res   = i + 1

    return res

When does this pattern show up?

This is the greedy skip pattern: when a partial solution definitively fails, everything that led to it is also ruled out, so you leap forward instead of backtracking.

Same reasoning in other problems

• Jump Game — if you can't reach position i, nothing past it is reachable. Skip.
• Jump Game II — track the furthest reachable point; greedily jump at each horizon.
• Candy — two passes (left-to-right, right-to-left) each make greedy local decisions.
• Partition Labels — once you know the last occurrence of a character, that entire range is committed.

Why the global check works

The problem guarantees at most one solution. So "is there a solution?" is answered bysum(gas) ≥ sum(cost). The greedy scan finds which station it is. These two questions are cleanly separable — that's what makes the O(n) solution elegant.

Where people go wrong

Skipping the global sum check

Without sum(gas) < sum(cost) → return -1, the greedy loop may return a bogus res even when no solution exists. The global check is mandatory.

Setting res = i instead of i + 1

When total goes negative at station i, station iitself is already proven to fail (you just couldn't leave it with enough fuel). The new candidate must be i + 1, not i.

Not understanding why skipped stations are invalid

If starting at res you run dry at i, then starting at any station k between res and i is also impossible — you'd arrive at i with strictly less fuel (you missed the gas fromres..k-1). This is the core invariant that makes the greedy skip valid.

Quick tests

• gas=[2], cost=[2] → 0 (single station, exact match)
• gas=[1,2], cost=[2,1] → 1 (start at 1, collect 2, travel cost 1, arrive at 0, collect 1, travel cost 2 = 0, done)
• gas=[1,2,3], cost=[2,3,2] → -1 (sum gas=6 < sum cost=7)

What to do next

• Jump GameMediumSame greedy skip logic — track how far you can reach, advance the horizon greedily.›
• Jump Game IIMediumExtend Jump Game — greedy BFS layer by layer for minimum jumps.›
• CandyHardTwo-pass greedy — each pass enforces one constraint locally, the combination gives the global optimum.›
• Partition LabelsMediumGreedy intervals — commit a partition once you know the last occurrence of each character.›