290. Gas Station
🔗 LeetCode Problem: 134. Gas Station
📊 Difficulty: Medium
🏷️ Topics: Array, Greedy
Problem Statement
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
Travel to station 2. Your tank = 3 - 4 = -1. 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^5
- 0 <= gas[i], cost[i] <= 10^4
🌳 Visual Understanding - The Gas Station Problem
The Problem We're Solving:
Circular route with n gas stations:
Station 0
↓ cost[0]
Station 1
↓ cost[1]
Station 2
↓ cost[2]
...
↓ cost[n-2]
Station n-1
↓ cost[n-1]
(back to Station 0)
At each station i:
- Fill up gas[i] units
- Need cost[i] units to reach next station
Question: From which station can we complete the circuit?
Understanding the Journey:
Example: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Station 0: gas=1, cost to next=3
┌─[1]─┐
│ ↓ need 3
Station 1: gas=2, cost to next=4
┌─[2]─┐
│ ↓ need 4
Station 2: gas=3, cost to next=5
┌─[3]─┐
│ ↓ need 5
Station 3: gas=4, cost to next=1
┌─[4]─┐
│ ↓ need 1
Station 4: gas=5, cost to next=2
┌─[5]─┐
│ ↓ need 2
(back to Station 0)
Net gain/loss at each station:
Station 0: 1 - 3 = -2 (lose 2)
Station 1: 2 - 4 = -2 (lose 2)
Station 2: 3 - 5 = -2 (lose 2)
Station 3: 4 - 1 = +3 (gain 3) ✓
Station 4: 5 - 2 = +3 (gain 3) ✓
Key Observations:
1. CIRCULAR route
After station n-1, you return to station 0
2. Start with EMPTY tank
Tank = 0 initially
3. Must complete ENTIRE circuit
Visit all n stations and return to start
4. At each station:
Tank = (previous tank) + gas[i] - cost[i]
Must have Tank >= 0 at all times!
5. If solution exists, it's UNIQUE
Only ONE starting station works
🧠 The AHA Moment - Why Greedy Works
The Brute Force Observation:
Try every station as starting point:
For station 0: Simulate complete journey
For station 1: Simulate complete journey
For station 2: Simulate complete journey
...
This is O(n²) - too slow for n = 10^5! 😰
The Key Insights:
Insight 1: Total Gas Must Be Enough
For ANY solution to exist:
sum(gas) must be >= sum(cost)
Why?
Total gas available = sum(gas)
Total gas needed = sum(cost)
If sum(gas) < sum(cost):
→ Not enough gas in total!
→ No starting point will work! ✗
This is a NECESSARY condition!
Insight 2: The Greedy Choice
If we start from station A and can't reach station B:
→ ANY station between A and B also can't reach B!
Why?
If starting from A, we run out before B
→ We had extra gas accumulated from A
→ Starting from middle (say C) has LESS gas than starting from A
→ So C definitely can't reach B either!
Therefore: If we fail at station B starting from A,
next try should start from B+1, not A+1!
This is the GREEDY insight! 🎯
Insight 3: Single Pass Solution
Because of Insight 2:
- Try starting from station 0
- If we fail at station k, next start = k+1
- Keep going...
- If we reach end, the last start position is answer!
Only ONE pass needed! O(n)! ✨
Visual Discovery of Greedy Property:
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
net = [-2,-2,-2,+3,+3]
Try starting from station 0:
Station 0: tank = 0 + 1 = 1
Travel to 1: 1 - 3 = -2 ✗ (FAILED!)
Can't reach station 1 from station 0.
KEY OBSERVATION:
Starting from 0, we had tank=1
Still couldn't reach station 1 (needed 3)
If we start from station 0 with 0 tank and fail,
there's NO WAY starting from between 0 and 1 will work!
(We'd have even less gas!)
So next try: start from station 1!
Try starting from station 1:
Station 1: tank = 0 + 2 = 2
Travel to 2: 2 - 4 = -2 ✗ (FAILED!)
Can't reach station 2 from station 1.
SAME LOGIC:
Starting from 1 with accumulated gas couldn't reach 2
So no point trying anything between 0 and 2
Next try: start from station 2!
Try starting from station 2:
Station 2: tank = 0 + 3 = 3
Travel to 3: 3 - 5 = -2 ✗ (FAILED!)
Next try: start from station 3!
Try starting from station 3:
Station 3: tank = 0 + 4 = 4
Travel to 4: tank = 4 - 1 = 3 ✓
Station 4: tank = 3 + 5 = 8
Travel to 0: tank = 8 - 2 = 6 ✓
Station 0: tank = 6 + 1 = 7
Travel to 1: tank = 7 - 3 = 4 ✓
Station 1: tank = 4 + 2 = 6
Travel to 2: tank = 6 - 4 = 2 ✓
Station 2: tank = 2 + 3 = 5
Travel to 3: tank = 5 - 5 = 0 ✓
Reached starting point! Answer: 3 ✓
🔴 Approach 1: Brute Force Simulation
📐 Function Definition
Function Signature:
int canCompleteCircuit(int[] gas, int[] cost)
What it does: - Try EACH station as starting point - For each start, simulate the entire journey - If journey completes, return that starting station - If no station works, return -1
💡 Intuition
"Try every possible starting station"
For each station i as start:
Simulate journey starting from i
Keep track of gas tank
If tank ever goes negative → this start doesn't work
If complete circuit → found answer!
Straightforward but slow!
📝 Implementation
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
// Try each station as starting point
for (int start = 0; start < n; start++) {
if (canCompleteFromStart(gas, cost, start)) {
return start;
}
}
return -1; // No solution
}
private boolean canCompleteFromStart(int[] gas, int[] cost, int start) {
int n = gas.length;
int tank = 0;
// Simulate journey starting from 'start'
for (int count = 0; count < n; count++) {
int station = (start + count) % n; // Circular index
// Fill gas at current station
tank += gas[station];
// Travel to next station
tank -= cost[station];
// If tank goes negative, can't proceed
if (tank < 0) {
return false;
}
}
return true; // Completed circuit!
}
}
🔍 Dry Run: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TRY START = 0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
tank = 0
Station 0: tank = 0 + 1 - 3 = -2 ✗
Can't proceed! Return false.
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TRY START = 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
tank = 0
Station 1: tank = 0 + 2 - 4 = -2 ✗
Can't proceed! Return false.
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TRY START = 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
tank = 0
Station 2: tank = 0 + 3 - 5 = -2 ✗
Can't proceed! Return false.
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TRY START = 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
tank = 0
Station 3: tank = 0 + 4 - 1 = 3 ✓
Station 4: tank = 3 + 5 - 2 = 6 ✓
Station 0: tank = 6 + 1 - 3 = 4 ✓
Station 1: tank = 4 + 2 - 4 = 2 ✓
Station 2: tank = 2 + 3 - 5 = 0 ✓
Completed circuit! Return true.
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: Start = 3 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
📊 Complexity Analysis
Time Complexity: O(n²)
Outer loop: Try n starting points
Inner loop: Simulate n stations for each start
Total: O(n) × O(n) = O(n²)
Too slow for n = 10^5! ⚠️
Space Complexity: O(1)
Only using variables, no extra arrays
🟢 Approach 2: Greedy - One Pass Solution (Optimal)
🎨 Building Deep Intuition - Understanding WHY Greedy Works
Let me show you the greedy insight with DETAILED reasoning:
Step 1: The Fundamental Total Gas Check
Before trying to find a starting station, ask:
"Is there enough total gas to complete the circuit?"
Total gas available: sum(gas) = gas[0] + gas[1] + ... + gas[n-1]
Total gas needed: sum(cost) = cost[0] + cost[1] + ... + cost[n-1]
If sum(gas) < sum(cost):
→ Not enough gas in the entire system!
→ No matter where you start, you'll run out!
→ Return -1 immediately!
If sum(gas) >= sum(cost):
→ Enough gas exists in total!
→ A solution MUST exist!
→ Now we just need to FIND where to start!
This check is CRUCIAL! 🔑
Step 2: The Core Greedy Insight - With Detailed Example
Let me show you WHY the greedy approach works with a clear example:
gas = [1, 3, 2, 4, 5]
cost = [2, 1, 5, 1, 2]
Attempt 1: Start from Station 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
JOURNEY: Station 1 → Station 2 → Station 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
At Station 1 (START):
Tank: 0 (empty start)
Fill: gas[1] = 3
Tank after fill: 0 + 3 = 3
Travel Station 1 → Station 2:
Cost: cost[1] = 1
Tank after travel: 3 - 1 = 2 ✓ (Success! Reached Station 2)
At Station 2:
Tank: 2 (arrived with 2 from Station 1)
↑ THIS IS BONUS GAS!
Fill: gas[2] = 2
Tank after fill: 2 + 2 = 4
Travel Station 2 → Station 3:
Cost: cost[2] = 5
Tank after travel: 4 - 5 = -1 ✗ (FAILED! Can't reach Station 3)
RESULT: Starting from Station 1, we CANNOT reach Station 3!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
The Key Question: Should We Try Station 2?
Let's compare TWO scenarios side by side:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
SCENARIO A: Starting from Station 1 (what we just tried)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Station 1:
Tank: 0 (start)
Fill: +3
Tank: 3
Travel to Station 2 (cost 1):
Tank: 3 - 1 = 2
Station 2:
Tank: 2 (arrived with 2 units from Station 1 - BONUS!)
Fill: +2
Tank: 4 (we have 4 units leaving Station 2)
Travel to Station 3 (cost 5):
Tank: 4 - 5 = -1 ✗ FAILED!
Key Point: We had 4 units when leaving Station 2
But 4 < 5, so we FAILED!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
SCENARIO B: Starting from Station 2 (should we try this?)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Station 2:
Tank: 0 (fresh start - NO BONUS!)
Fill: +2
Tank: 2 (we have only 2 units leaving Station 2)
Travel to Station 3 (cost 5):
Tank: 2 - 5 = -3 ✗ FAILED!
Key Point: We have only 2 units when leaving Station 2
But 2 < 5, so we FAILED even worse!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
THE COMPARISON - THE AHA MOMENT! 🎯
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Gas when leaving Station 2 Can reach Station 3?
↓ ↓
Scenario A: 4 units NO (4 < 5)
Scenario B: 2 units NO (2 < 5)
If 4 units wasn't enough to reach Station 3,
how can 2 units (which is LESS) be enough?
IMPOSSIBLE!
Therefore: Don't waste time trying Station 2!
We already know it will fail!
The Reasoning - Why Station 2 Will Definitely Fail
Think about what happened:
When we started from Station 1:
1. We began with empty tank (0 units)
2. We filled at Station 1 (got 3 units)
3. We traveled to Station 2 (spent 1 unit)
4. We arrived at Station 2 with 2 units in tank
5. This 2 units is EXTRA gas we brought from Station 1!
6. We filled at Station 2 (got 2 more units)
7. Total at Station 2: 2 (carried) + 2 (filled) = 4 units
8. We tried to reach Station 3 (needs 5 units)
9. We FAILED because 4 < 5
Now imagine starting fresh from Station 2:
1. We begin with empty tank (0 units)
2. We fill at Station 2 (got 2 units)
3. Total at Station 2: 0 (carried) + 2 (filled) = 2 units
4. We try to reach Station 3 (needs 5 units)
5. We will FAIL because 2 < 5
The difference:
Starting from Station 1: We had BONUS of 2 units from the journey
Starting from Station 2: We have NO BONUS (starting fresh)
With bonus, we had 4 units → Failed
Without bonus, we have 2 units → Will definitely fail!
CONCLUSION: If we can't reach Station 3 from Station 1 (with accumulated gas),
we definitely can't reach Station 3 from Station 2 (without accumulated gas)!
So skip Station 2 entirely!
Next try: Station 3!
Step 3: The General Greedy Rule
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
THE GREEDY PROPERTY (Now you understand WHY!)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
If you start from station A and fail to reach station B:
→ You had accumulated gas from the journey A to B-1
→ Even with this accumulated gas, you couldn't reach B
→ Any station between A and B-1 has LESS accumulated gas than you did
→ So they will ALL fail to reach B too!
Therefore:
→ Skip ALL stations from A to B-1
→ Next starting candidate: Station B itself!
This is the GREEDY insight that reduces O(n²) to O(n)! 🎯
Visual Analogy - The Running Start
Think of it like running and jumping over a gap:
Scenario A: Starting from Station 1
Station 1 Station 2 Station 3
(Start) (Checkpoint) (Destination)
│ │ │
│ │ │
└──running start───┤ │
(momentum!) └────try to jump─────────┤
(you have speed from │
running from 1!) │
✗ Still can't make it!
Scenario B: Starting from Station 2
Station 2 Station 3
(Start from (Destination)
standstill)
│ │
│ │
└────try to jump─────────┤
(you have NO speed, │
starting fresh!) │
✗ Even worse!
If you can't make the jump WITH a running start (momentum),
you definitely can't make it starting from a standstill!
This is why we skip Station 2 when we fail from Station 1! 🏃
Step 4: The Complete Algorithm
Algorithm Logic:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
1. CHECK TOTAL BALANCE:
If sum(gas) < sum(cost):
→ Not enough gas total
→ Return -1 immediately
2. FIND STARTING STATION:
start = 0 (try starting from station 0)
tank = 0 (empty tank)
For each station i from 0 to n-1:
a. Calculate net gain/loss: tank += (gas[i] - cost[i])
b. If tank goes negative:
- Can't reach station i+1 from current start
- By greedy property: ALL stations from start to i also can't reach i+1
- So set start = i+1 (skip all failed stations)
- Reset tank = 0
3. RETURN ANSWER:
Return start
Why no verification needed?
- We checked sum(gas) >= sum(cost), so solution EXISTS
- We ruled out all other stations via greedy property
- The last 'start' we set is THE answer!
📝 Implementation - Now You Understand It!
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
// STEP 1: Check if solution is even possible
int totalGas = 0;
int totalCost = 0;
for (int i = 0; i < n; i++) {
totalGas += gas[i];
totalCost += cost[i];
}
if (totalGas < totalCost) {
return -1; // Not enough gas in total - impossible!
}
// STEP 2: Find the starting station
// (We know solution exists because totalGas >= totalCost)
int start = 0; // Current starting candidate
int tank = 0; // Current gas in tank
for (int i = 0; i < n; i++) {
// Add gas at station i, subtract cost to travel to i+1
tank += gas[i] - cost[i];
// If tank goes negative, we can't reach station i+1 from current start
if (tank < 0) {
// By greedy property: ALL stations from 'start' to 'i' will fail
// So next candidate is i+1
start = i + 1;
tank = 0; // Reset tank for new start
}
}
return start;
}
}
🔍 Complete Dry Run With Understanding
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 1: Total Balance Check
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
totalGas = 1 + 2 + 3 + 4 + 5 = 15
totalCost = 3 + 4 + 5 + 1 + 2 = 15
totalGas >= totalCost? YES (15 >= 15)
→ Solution EXISTS! Now find where to start...
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 2: Find Starting Station
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
start = 0
tank = 0
───────────────────────────────────────────────────────
i = 0: gas[0]=1, cost[0]=3
───────────────────────────────────────────────────────
tank = 0 + (1 - 3) = -2
Tank negative! ✗
Understanding:
Started from Station 0 with empty tank
Filled 1 unit at Station 0
Need 3 units to reach Station 1
Only have 1 unit → Can't reach Station 1!
Greedy Decision:
Station 0 failed to reach Station 1
So Station 0 won't work!
Next candidate: start = 1
Reset: tank = 0
───────────────────────────────────────────────────────
i = 1: gas[1]=2, cost[1]=4
───────────────────────────────────────────────────────
tank = 0 + (2 - 4) = -2
Tank negative! ✗
Understanding:
Started from Station 1 with empty tank
Filled 2 units at Station 1
Need 4 units to reach Station 2
Only have 2 units → Can't reach Station 2!
Greedy Decision:
Station 1 failed to reach Station 2
So Stations 0 and 1 both won't work!
Next candidate: start = 2
Reset: tank = 0
───────────────────────────────────────────────────────
i = 2: gas[2]=3, cost[2]=5
───────────────────────────────────────────────────────
tank = 0 + (3 - 5) = -2
Tank negative! ✗
Understanding:
Started from Station 2 with empty tank
Filled 3 units at Station 2
Need 5 units to reach Station 3
Only have 3 units → Can't reach Station 3!
Greedy Decision:
Station 2 failed to reach Station 3
So Stations 0, 1, 2 all won't work!
Next candidate: start = 3
Reset: tank = 0
───────────────────────────────────────────────────────
i = 3: gas[3]=4, cost[3]=1
───────────────────────────────────────────────────────
tank = 0 + (4 - 1) = 3
Tank positive! ✓
Understanding:
Started from Station 3 with empty tank
Filled 4 units at Station 3
Need 1 unit to reach Station 4
Have 4 units → Can reach Station 4!
After travel: 4 - 1 = 3 units remaining
No action needed, continue with start = 3
───────────────────────────────────────────────────────
i = 4: gas[4]=5, cost[4]=2
───────────────────────────────────────────────────────
tank = 3 + (5 - 2) = 6
Tank positive! ✓
Understanding:
At Station 4 with 3 units from previous travel
Filled 5 units at Station 4
Total: 3 + 5 = 8 units
Need 2 units to reach Station 0 (circular)
After travel: 8 - 2 = 6 units remaining
No action needed, continue with start = 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
start = 3
Return 3 ✓
Why this is correct:
- Stations 0, 1, 2 were ruled out (tank went negative)
- From Station 3, tank stayed positive through end
- Total balance is positive, so solution exists
- By greedy property, Station 3 is THE answer!
No need to verify by simulating full circuit!
The greedy property guarantees it works! ✨
🎯 Why No Verification Needed - The Beautiful Proof
Question: "Why don't we need to verify the answer by simulating the full circuit?"
Answer:
We proved two things:
1. SOLUTION EXISTS:
sum(gas) >= sum(cost)
→ There's enough gas in total
→ SOME starting station must work
2. ALL OTHER STATIONS RULED OUT:
Stations 0, 1, 2 were ruled out (tank went negative)
→ They can't complete the circuit
3. ONLY ONE CANDIDATE LEFT:
Station 3 is the only candidate left
→ By elimination, it MUST be the answer!
4. WHY CIRCULAR PART WORKS:
From Station 3 to end: tank = 6 (surplus!)
From Station 0 to 2: net = (1-3) + (2-4) + (3-5) = -6 (deficit)
Surplus (6) exactly covers deficit (-6)!
→ We can complete the circular part!
This is the beauty of the greedy approach:
- Total balance check ensures solution exists
- Greedy elimination finds the unique solution
- No verification needed! 🎯
📊 Complexity Analysis
Time Complexity: O(n)
Pass 1: Calculate total gas and cost → O(n)
Pass 2: Find starting station → O(n)
Total: O(n)
OPTIMAL! Can't do better than O(n)! ✨
Space Complexity: O(1)
Only using a few variables
No extra arrays or data structures
Constant space!
💡 Alternative Greedy Implementation
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int totalSurplus = 0; // Total gas surplus
int currentSurplus = 0; // Surplus from current start
int start = 0;
for (int i = 0; i < n; i++) {
int surplus = gas[i] - cost[i];
totalSurplus += surplus;
currentSurplus += surplus;
// If current surplus negative, reset start
if (currentSurplus < 0) {
start = i + 1;
currentSurplus = 0;
}
}
// Check if solution exists
return totalSurplus >= 0 ? start : -1;
}
}
This version: - Calculates total surplus while finding start - Slightly more elegant - Same complexity: O(n) time, O(1) space
🎯 Key Insights Summary
The Three Critical Points:
1. Total Gas Check
sum(gas) >= sum(cost) → Solution exists
sum(gas) < sum(cost) → No solution possible
This is NECESSARY and SUFFICIENT!
2. The Greedy Property
If you fail at station B starting from A:
→ All stations from A to B-1 also fail
→ Next try: start from B
This eliminates O(n²) redundant checks!
3. Single Pass Sufficiency
Because solution is UNIQUE (if it exists):
→ One pass to rule out stations
→ Last candidate is THE answer
→ No need to verify!
📝 Quick Revision Notes
🎯 Core Concept
Problem: Find starting gas station to complete circular route
Key Observation: If sum(gas) >= sum(cost), solution exists and is unique
Greedy Strategy: 1. Check total gas vs total cost 2. Scan once: if tank goes negative, move start forward 3. Return final start position
Why It Works: - Failing from A to B means all A to B-1 also fail - Total balance ensures remaining part is completable
⚡ Quick Implementation
import java.util.Arrays;
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
// return naive(gas, cost);
return greedy(gas, cost);
}
private int greedy(int[] gas, int[] cost) {
// step 1: immediate check (cost should be always less than gas)
int sumGas = Arrays.stream(gas).sum();
int sumCost = Arrays.stream(cost).sum();
if (sumCost > sumGas) {
return -1;
}
// step 2: start from station 0 and proceed till
// you cannot reach next station
int fuelSpent = 0;
int startStation = 0;
for (int currStation = 0; currStation < gas.length; currStation++) {
fuelSpent = fuelSpent + gas[currStation] - cost[currStation];
// step 3: once you cannot move next station (when fuelSpent < 0), we
// need to start from the next station (like we are trying every station
// in the naive method)
// Suppose, we started at station 0 and got fuel spent -ve at station 3
// We need to reset fuel spent and startStation becomes 4.
// Why start will not become any of 1, 2 or 3?
// Greedy concept: If we are not able to reach station 3 from station 0, we
// cannot reach from any of other stations like 1 or 2.
// If we see formula:
// fuelSpent = fuelSpent + gas[currStation] - cost[currStation]
// fuelSpent adds +ve. station 0 already adds extra gas.
// If with that only, we are not able to means, we cannot do with station 1 or 2
if (fuelSpent < 0) {
fuelSpent = 0;
startStation = currStation + 1;
}
}
return startStation;
}
private int naive(int[] gas, int[] cost) {
int n = gas.length;
// step 1: start trying from every station
// check if we can complete the circuit starting from this station
for (int station = 0; station < n; station++) {
if (canComplete(gas, cost, station)) {
return station;
}
}
return -1;
}
private boolean canComplete(int[] gas, int[] cost, int station) {
int n = gas.length;
int fuelSpent = 0;
// step 2: go station by station from the current station
for (int i = 0; i < n; i++) {
int currStation = (station + i) % n;
// step 3: fuel spent to travel from this station
// to next station (i to i + 1)
fuelSpent = fuelSpent + gas[currStation] - cost[currStation];
// step 4: return immediately if not possible
if (fuelSpent < 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.canCompleteCircuit(new int[] { 1, 2, 3, 4, 5 }, new int[] { 3, 4, 5, 1, 2 }) == 3);
}
}
🔑 Key Points
✓ CIRCULAR route (after last station, back to first)
✓ Check total gas >= total cost FIRST
✓ If solution exists, it's UNIQUE
✓ Greedy: move start forward when tank negative
✓ ONE pass sufficient (O(n))
✓ No need to verify answer (guaranteed by total balance)
🎪 Memory Aid
"Total balance check first!"
"Tank negative? Move start forward!"
"One pass finds the unique answer!"
"Greedy works because failures eliminate ranges!" ✨
⚠️ Common Mistakes
// Mistake 1: Not checking total first
for (int start = 0; start < n; start++) {
// Try each start...
}
// ❌ Wastes time if solution doesn't exist!
// ✓ CORRECT: Check first
if (sum(gas) < sum(cost)) return -1;
// Mistake 2: Moving start by 1 instead of to failure point
if (tank < 0) {
start++; // ❌ Wrong! Still O(n²)
}
// ✓ CORRECT: Jump to failure point
if (tank < 0) {
start = i + 1; // Skip all stations up to failure
}
// Mistake 3: Trying to verify the answer
// ❌ No need! If total balance is positive and we found start,
// it's guaranteed to work!
// Mistake 4: Not resetting tank
if (tank < 0) {
start = i + 1;
// ❌ Forgot to reset tank!
}
// ✓ CORRECT
if (tank < 0) {
start = i + 1;
tank = 0; // Reset!
}
🎓 Practice Exercises
Exercise 1: Trace Yourself
Trace the greedy algorithm on:
gas = [2,3,4]
cost = [3,4,3]
totalGas = ?
totalCost = ?
Solution exists? ?
i=0: tank=?, start=?
i=1: tank=?, start=?
i=2: tank=?, start=?
Answer: ?
(Solution: No solution exists, return -1)
Exercise 2: Edge Cases
What's the answer for these?
1. gas = [5], cost = [4]
Answer: ?
2. gas = [2], cost = [2]
Answer: ?
3. gas = [1,2,3,4,5], cost = [5,4,3,2,1]
Answer: ?
(Solutions: 0, 0, 0)
🎉 Congratulations!
You've mastered the Gas Station problem!
What You Learned:
✅ Brute Force - Try all starts O(n²)
✅ Greedy Optimization - One pass O(n)
✅ Total Balance - Necessary and sufficient condition
✅ Greedy Property - Failure eliminates ranges
✅ Proof of Correctness - Why greedy works
The Beautiful Insight:
Complex Problem → Simple Greedy Solution
Two key insights:
1. Total gas check tells us IF solution exists
2. Greedy scan tells us WHERE the solution is
The magic:
Failing at position B from start A means:
ALL positions A to B-1 also fail!
This single insight reduces O(n²) to O(n)!
This is the power of Greedy:
Find the property that eliminates redundant work
One clever observation → Massive speedup! 🎯
Interview Mastery:
When asked about Gas Station:
1. Understand the problem: "Circular route, find starting station"
2. Brute force: "Try each station - O(n²)"
3. Key insight: "Check total gas first!
If sum(gas) < sum(cost), no solution"
4. Greedy insight: "If fail at B from A,
all A to B-1 also fail. Jump to B!"
5. Code it: Clean O(n) solution
6. Explain correctness: "Total balance + greedy property
guarantee the answer"
Shows deep understanding! 💯
You've mastered an elegant greedy algorithm! 🚀✨🎯