Gas Station

Difficulty: Medium
Topics: Array, Greedy
Link: https://leetcode.com/problems/gas-station/

Problem Description

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

Example 1:


Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:


Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Constraints:

n == gas.length == cost.length
1 <= n <= 105
0 <= gas[i], cost[i] <= 104
The input is generated such that the answer is unique.

Solution

1. Problem Deconstruction

Technical Restatement:
Given two integer arrays gas (fuel available at each station) and cost (fuel required to reach the next station) of length n, representing a circular route, determine the unique starting index such that a vehicle with an empty tank can complete a full clockwise circuit. The vehicle gains gas[i] at station i and expends cost[i] to reach station (i+1) mod n. Return -1 if no valid starting point exists.

Beginner-Friendly Explanation:
Imagine a circular road with gas stations. At each station, you can collect a certain amount of gas, but it costs gas to drive to the next station. You start with an empty tank. Your goal is to find which station to start at so that you can drive all the way around the circle without running out of gas. If it’s impossible, return -1.

Mathematical Formulation:
Let $g_i$ = gas[i], $c_i$ = cost[i]. For a starting index $s$ , define the cumulative fuel balance at step $k$ as:

T_k = \sum_{i=0}^{k} (g_{(s+i) \mod n} - c_{(s+i) \mod n})

We require $T_k \geq 0$ for all $k \in [0, n-1]$ and $T_{n-1} + (g_{s-1} - c_{s-1}) \geq 0$ (completing the circle). Alternatively, the net fuel gain per station is $\Delta_i = g_i - c_i$ . The problem reduces to finding $s$ such that all partial sums of the cyclic sequence $\{\Delta_s, \Delta_{s+1}, ..., \Delta_{s+n-1}\}$ are non-negative.

Constraint Analysis:

n == gas.length == cost.length: Ensures arrays are aligned. Implies no missing data.
1 <= n <= 10^5: Rules out O( $n^2$ ) brute-force solutions (1e5² = 10e10 operations, infeasible). Requires O( $n$ ) or O( $n$ log $n$ ).
0 <= gas[i], cost[i] <= 10^4: No negative values. Zero values are valid (e.g., a station with no gas or a leg requiring no fuel).
Unique solution guarantee: Simplifies logic; we don’t need to handle multiple valid starting points.

Hidden Edge Cases:

All stations have zero gas but positive cost → impossible.
Total gas < total cost → impossible (but converse isn’t sufficient; distribution matters).
Single station: $g_0 \geq c_0$ required (since you need to return to start).
A station with $g_i = 0$ and $c_i = 0$ is neutral but must be traversable.

2. Intuition Scaffolding

Analogies:

Real-World Metaphor: Like planning a road trip where you withdraw cash (gas) at each city but must pay tolls (cost). You need to start where your wallet never goes negative.
Gaming Analogy: In a survival game, you collect resources at checkpoints but consume them to move. You must choose a starting checkpoint to complete the cycle without starvation.
Math Analogy: Finding a cyclic shift of a sequence where all prefix sums are non-negative—akin to a “positive cumulative balance” condition in a circular buffer.

Common Pitfalls:

Starting at the station with highest gas: Fails if that station is preceded by a high-cost segment.
Starting where gas[i] - cost[i] is maximum: Doesn’t guarantee subsequent segments are sustainable.
Assuming total gas >= total cost is sufficient: While necessary, it doesn’t ensure a valid path (e.g., a large negative segment early can break the chain).
Using greedy reset without tracking total surplus: Might miss the optimal start point.
Ignoring circularity: Treating the array as linear and missing wrap-around effects.

3. Approach Encyclopedia

Brute Force Approach:
Try every starting index. For each, simulate the full circuit.

def canCompleteCircuit(gas, cost):
    n = len(gas)
    for start in range(n):
        tank = 0
        for i in range(n):
            station = (start + i) % n
            tank += gas[station] - cost[station]
            if tank < 0:
                break
        if tank >= 0:
            return start
    return -1

Complexity Proof:
Time: O( $n^2$ ) — for each start, we do O( $n$ ) operations. For $n=10^5$ , worst-case ~10e10 operations, which is infeasible. Space: O(1).

Visualization:

Station: 0   1   2   3   4  
Gas:    [1,  2,  3,  4,  5]  
Cost:   [3,  4,  5,  1,  2]  
Δ:      [-2, -2, -2, 3,  3]  

Brute-force check for start=3:
Step0: station3 → tank=0+3=3
Step1: station4 → tank=3+3=6
Step2: station0 → tank=6-2=4
Step3: station1 → tank=4-2=2
Step4: station2 → tank=2-2=0 → valid.

Optimal Approach (Greedy with Cumulative Balance):
Key insight: If total gas >= total cost, a solution exists. We can traverse linearly while tracking cumulative fuel. If at point i, the tank becomes negative, reset the start to i+1.
Why it works: The circular route can be “unrolled”. The starting point must be after where the cumulative fuel is most negative.

Pseudocode:

1. total_surplus, current_surplus, start = 0
2. For i in range(n):
3.   total_surplus += gas[i] - cost[i]
4.   current_surplus += gas[i] - cost[i]
5.   If current_surplus < 0:
6.      current_surplus = 0
7.      start = i+1
8. Return start if total_surplus >=0 else -1

Complexity Proof:
Time: O( $n$ ) — single pass. Space: O(1).
Derivation: Each station is visited exactly once. Operations per station are constant time (addition and comparison).

Visualization:
Using Example 1:

i | gas[i]-cost[i] | total_surplus | current_surplus | start  
0 | -2             | -2            | -2 (reset)      | 1  
1 | -2             | -4            | -2 (reset)      | 2  
2 | -2             | -6            | -2 (reset)      | 3  
3 | 3              | -3            | 3               | 3  
4 | 3              | 0             | 6               | 3

Since total_surplus=0 >=0, start=3 is valid.

4. Code Deep Dive

Annotated Optimal Solution:

def canCompleteCircuit(gas, cost):
    n = len(gas)
    total_surplus = 0    # Tracks overall net fuel (must be >=0 for solution to exist)
    current_surplus = 0   # Tracks fuel from current candidate start
    start = 0             # Candidate starting index
    for i in range(n):
        total_surplus += gas[i] - cost[i]
        current_surplus += gas[i] - cost[i]
        if current_surplus < 0:
            # Current path is invalid. Reset start to next station.
            current_surplus = 0
            start = i + 1   # Since i failed, try i+1
    # If total_surplus >=0, a solution exists and 'start' is the unique answer.
    return start if total_surplus >= 0 else -1

Edge Case Handling:

Example 2: gas = [2,3,4], cost = [3,4,3]
Δ = [-1, -1, 1]. total_surplus = -1 → returns -1.
All zero cost: If all cost[i]=0, any start works (but unique guarantee implies one valid? Actually, all are valid, but the problem says unique, so likely not tested).
Single station: gas[0] >= cost[0]? For n=1, loop sets start=0, checks total_surplus.

5. Complexity War Room

Hardware-Aware Analysis:

For $n=10^5$ , the solution does ~100,000 operations.
Memory: Only 3 integers (~24 bytes), fitting in L1 cache.
Predictable linear access pattern → CPU prefetching friendly.

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute Force	O( $n^2$ )	O(1)	High (9/10)	❌ Fails large n
Greedy Cumulative	O( $n$ )	O(1)	Medium (7/10)	✅ Optimal

6. Pro Mode Extras

Variants:

Multiple Circuits: If you can complete the circuit multiple times, the same solution holds (but requires checking total_surplus >=0 for each cycle).
Two Transactions (LC 123): Not directly applicable, but similar cumulative techniques appear in array problems.
Minimum Starting Fuel: Instead of empty tank, find the minimum initial fuel required.

Interview Cheat Sheet:

First Mention: “This is a circular array problem with cumulative sums. The optimal solution is O(n) time and O(1) space.”
Key Insight: “If the total fuel is non-negative, a solution exists. The starting point must be after the largest cumulative deficit.”
Common Trap: “Don’t assume the station with the highest gas or highest net gain is the best start.”
Verification: “Always check the total surplus first to avoid unnecessary computation.”

#134 - Gas Station