Gas Station

Medium🏃 GreedyArrayGreedy

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

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the i^th 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 <= 10⁵
0 <= gas[i], cost[i] <= 10⁴
The input is generated such that the answer is unique.

Pattern Recognition & Intuition

Why this is a Greedy problem

🏃

Greedy

Always pick the locally optimal choice — and prove it works globally.

A greedy algorithm makes the best-looking choice at each step without reconsidering past decisions. It works when the "greedy choice property" holds: local optima lead to global optimum. The hard part isn't the code — it's proving (or recognizing) when greedy is valid.

MENTAL MODEL

Sort by the right criterion, then make the greedy choice. Prove correctness by exchange argument: "swapping the greedy choice for any other choice can only make things worse or equal."

INTUITION

For "Jump Game": at each position, greedily track the farthest index you can reach. You don't need to try all paths — if the max reachable index ever covers position i, you can be there. Greedy works because reaching farther is always at least as good as reaching less far.

SIGNALS — WHEN TO USE THIS PATTERN

"Jump game", "jump game II" — track max reachable index
"Gas station" — circular greedy: if total gas >= total cost, a solution exists
"Meeting rooms", "interval scheduling" — sort by end time, greedily pick non-overlapping
"Task scheduler" — frequency-based greedy
"Minimum number of arrows", "partition labels" — interval greedy

Approaches & Trade-offs

From brute force to optimal — understand every step of the journey

BRUTE FORCE

Brute Force

⏱ O(2ⁿ) without memo; O(n²) with DP💾 O(n) recursion

✦ OPTIMAL

Optimal

⏱ O(n) single pass💾 O(1)

Make the locally optimal choice at each step. For jump game: track max reachable, count jumps only when you cross a boundary.

ALGORITHM STEPS

Initialize max_reach = 0, jumps = 0, curr_boundary = 0
For each index i from 0 to n-2: update max_reach = max(max_reach, i + nums[i])
When i == curr_boundary: we must jump here, jumps++, curr_boundary = max_reach
If curr_boundary >= n-1 at any point: done

TIME

O(n) single pass

SPACE

O(1)

The greedy key: within the current "zone" [prev_boundary+1 .. curr_boundary], always extend as far as possible.

def jump(nums):
    jumps = max_reach = curr_end = 0
    for i in range(len(nums) - 1):
        max_reach = max(max_reach, i + nums[i])
        if i == curr_end:          # must jump here
            jumps += 1
            curr_end = max_reach
    return jumps

Key Insight & Common Pitfalls

THE "AHA" MOMENT

Greedy algorithms are "obviously correct" once you see the right exchange argument. For interval scheduling: if you pick the interval that ends latest first, you can always swap it for the one ending soonest — and the count can only stay the same or improve. That's the exchange argument. If you can't construct this argument, greedy probably doesn't work and you need DP.

COMMON MISTAKES

✕Assuming greedy works without proof — test against counter-examples (coin change with non-standard denominations fails greedy)
✕Wrong sort criterion: for interval scheduling, sort by END time (not start, not length)
✕"Gas station": if total gas >= total cost, a solution definitely exists — start from where the running total hits a new minimum
✕Off-by-one: jump game loops to len(nums)-1 (not n), because you don't need a jump FROM the last position

PRO TIPS

›Exchange argument template: "Suppose we pick X instead of the greedy choice Y. Swapping X for Y gives result R' ≥ R."
›"Assign cookies": sort both, use two pointers — greedily match smallest sufficient cookie to each child
›"Lemonade change": greedily give largest bills first to preserve flexibility for larger change
›If stuck between greedy and DP: try greedy on small examples, check if it ever makes the wrong choice

Interactive Visualizer

Building 🏃 Greedy Visualization

Generating visualization…